LC 234回文链表Palindrome Linked List　简单

判断链表节点值正读反读是否相同（是否为回文）。

思路 快慢指针找中点，反转后半段，再与前半逐值比对。时间 O(n)，空间 O(1)。

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        pre, cur = None, slow
        while cur:
            nxt = cur.next
            cur.next = pre
            pre = cur
            cur = nxt
        while pre:
            if head.val != pre.val:
                return False
            head = head.next
            pre = pre.next
        return True