Leetcode 234. Palindrome Linked List

题目描述：判断一个链表是否为回文链表。

题目链接：234. Palindrome Linked List

要求O(1)空间，线性时间，那么想到一个快慢指针 然后记录前半段的val，然后利用slow向后逐个比较。栈，仍然占用了大量的空间。
最重要的是，当还有fast的时候，但是没有fast.next代表逐个为奇数，于是slow还要向前移动一个，这时slow是没有人与之匹配的。

想到异或有记忆功能，但是这样的话不能保证其顺序，只能保证左边的数字跟右边的数字相等。

###还有神仙解法：就是在找中点的时候翻转第一部分。

Solution 1: Reversed first half == Second half?
Phase 1: Reverse the first half while finding the middle.
Phase 2: Compare the reversed first half with the second half.
11 lines, 12 with restore, O(n) time, O(1) space

链表的题目无非就是快慢指针、去除第k个、翻转k、翻转链表、有环无环、排序翻转等组合操作。

代码如下：

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

class Solution:
    def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        slow,fast = head,head
        nhead = None
        while(fast and fast.next):
            fast = fast.next.next
            nhead, nhead.next, slow = slow, nhead, slow.next  #翻转操作
        
        if fast:
            slow = slow.next  #奇数
        while(nhead and nhead.val==slow.val):
            nhead  = nhead.next
            slow = slow.next
        return not nhead
  
        

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

class Solution:
    def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        slow,fast = head,head
        prev = []
        while(fast and fast.next):
            fast = fast.next.next
            prev.append(slow)
            slow = slow.next
        
        if fast:
            slow = slow.next  #奇数
        while(prev and slow):
            if prev.pop().val != slow.val:
                return False
            slow = slow.next
        if not prev and slow:
            return False
        if not slow and prev:
            return False
        return True