Given a singly linked list, determine if it is a palindrome.

Example 1:

Input: 1->2
Output: false

Example 2:

Input: 1->2->2->1
Output: true

Follow up:
Could you do it in O(n) time and O(1) space?

题意

判断链表是否是回文的

思路

1. 栈
   用一个栈存储链表所有结点的值，再对比出栈元素和正向遍历链表的值是否相等。

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        stack = []
        tmp = head
        while tmp:
            stack.append(tmp.val)
            tmp = tmp.next
        while head:
            cur = stack.pop()
            if head.val != cur:
                return False
            head = head.next
        return True

2. 快慢指针
   1.快慢指针找到链表的中点
   2.翻转链表前半部分
   3.回文校验

    def isPalindrome2(self, head: ListNode) -> bool:
        if head is None or head.next is None:
            return True
        slow = head
        fast = head
        new_head = None
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        while head != slow:
            nxt = head.next
            head.next = new_head
            new_head = head
            head = nxt
        # 如果是奇数个结点，去掉后半部分第一个结点
        if fast is not None:
            slow = slow.next
        while slow:
            if slow.val != new_head.val:
                return False
            slow = slow.next
            new_head = new_head.next
        return True