234 Palindrome Linked List

要求O(n) time and O(1) space

第一步： 找到中点

第二步： 翻转后半段

第三步：检查前半段和后半段是否相同

Python

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

class Solution:
    def reverseList(self, head):
        curr, prev = head, None
        while curr:
            nextt = curr.next
            curr.next = prev
            prev = curr
            curr = nextt
        return prev

    def isPalindrome(self, head: 'ListNode') -> 'bool':
        fast, slow = head, head
        prev = None
        while fast and fast.next:
            fast = fast.next.next
            prev = slow
            slow = slow.next
        if prev:
            prev.next = None
        else:
            return True
        t = self.reverseList(slow)
        while(t and head):
            if head.val != t.val:
                return False
            head = head.next
            t = t.next
        return True