234. Palindrome Linked List

[mengyushi]

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        '''
        1->2->2->1->None
        sf
           s  f
              s.    f

        1->2->3->2->1->None
        sf
           s  f
              s.    f 
        '''

        s = f = head

        while f and f.next:
            s = s.next
            f = f.next.next

        # reverse s

        '''
             s
        None 3->2->1->None
        pre  p
                   pre  p

        tail = 1->2->3->None

        '''

        pre = None
        p = s

        while p:
            next_p = p.next
            p.next = pre
            pre = p
            p = next_p

        tail = pre

        while tail:
            if head.val != tail.val:
                return False
            tail = tail.next
            head = head.next

        return True