-
BingoPython:
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: # @param {ListNode} head # @return {boolean} def isPalindrome(self, head): if head is None: return True #find mid node fast = slow = head while fast.next and fast.next.next: slow = slow.next fast = fast.next.next #reverse second half p, last = slow.next, None while p: next = p.next p.next = last last, p = p, next #check palindrome p1, p2 = last, head while p1 and p1.val == p2.val: p1, p2 = p1.next, p2.next #resume linked list(optional) p, last = last, None while p: next = p.next p.next = last last, p = p, next slow.next = last return p1 is None
-
BingoC++解法一:
class Solution { public: bool isPalindrome(ListNode* head) { if (!head || !head->next) return true; ListNode *slow = head, *fast = head; stack<int> s; s.push(head->val); while (fast->next && fast->next->next) { slow = slow->next; fast = fast->next->next; s.push(slow->val); } if (!fast->next) s.pop(); while (slow->next) { slow = slow->next; int tmp = s.top(); s.pop(); if (tmp != slow->val) return false; } return true; } };
-
BingoC++解法二:
class Solution { public: bool isPalindrome(ListNode* head) { if (!head || !head->next) return true; ListNode *slow = head, *fast = head; while (fast->next && fast->next->next) { slow = slow->next; fast = fast->next->next; } ListNode *last = slow->next, *pre = head; while (last->next) { ListNode *tmp = last->next; last->next = tmp->next; tmp->next = slow->next; slow->next = tmp; } while (slow->next) { slow = slow->next; if (pre->val != slow->val) return false; pre = pre->next; } return true; } };
-
BingoJava:
public boolean isPalindrome(ListNode head) { ListNode fast = head, slow = head; while (fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; } if (fast != null) { // odd nodes: let right half smaller slow = slow.next; } slow = reverse(slow); fast = head; while (slow != null) { if (fast.val != slow.val) { return false; } fast = fast.next; slow = slow.next; } return true; } public ListNode reverse(ListNode head) { ListNode prev = null; while (head != null) { ListNode next = head.next; head.next = prev; prev = head; head = next; } return prev; }
-