请判断一个链表是否为回文链表。

示例 1:

输入: 1->2
输出: false
示例 2:

输入: 1->2->2->1
输出: true
进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

解法一：快慢指针+链表反转

先利用快慢指针找到链表中点O(n)时间，然后反转后半段O(n)时间，最后遍历比较O(n)时间。空间复杂度为O(1)。

  1. class Solution:
  2.     def isPalindrome(self, head: ListNode) -> bool:
  3.         p = slow = fast = head
  4.         while fast and fast.next:
  5.             slow, fast = slow.next, fast.next.next
  6.         pre, cur = None, slow
  7.         while cur:
  8.             nxt = cur.next
  9.             cur.next = pre
  10.             pre, cur = cur, nxt
  11.         q = pre
  12.         while p and q:
  13.             if p.val != q.val:
  14.                 return False
  15.             p, q = p.next, q.next
  16.         return True

解法二：递归

利用递归反向遍历链表（有点类似二叉树的后序遍历）。这个方法用到递归外的变量来从head迭代整个链表，真是一个神奇的方法！虽然不符合空间O(1)的要求，但是这个解法值得记忆。

  1. class Solution:
  2.     def isPalindrome(self, head: ListNode) -> bool:
  3.         self.front = head
  5.         def recursive(cur) -> bool:
  6.             if not cur:
  7.                 return True
  8.             if not recursive(cur.next):
  9.                 return False
  10.             if self.front.val != cur.val:
  11.                 return False
  12.             self.front = self.front.next
  13.             return True
  15.         return recursive(head)