234. Palindrome Linked List

知识点：

• 快慢指针
• 链表反转
  链表反转的四行代码必须熟记

class Solution:
    def isPalindrome(self, head):
        # 找到链表终中点 考虑奇数偶数两种情况 最终slow的位置正中间（奇数） 中间偏右的节点（偶数）
        slow = fast = head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next

        # 翻转链表
        prev = self.InerseList(slow)

        # 顺序检查两个链表
        while prev:
            if prev.val != head.val:
                return False
            prev = prev.next
            head = head.next
        return True

    def InerseList(self, root):
        pre = None
        while root:
            tp = root.next
            root.next = pre
            pre = root
            root = tp

        return pre