题目

https://leetcode-cn.com/problems/palindrome-linked-list/

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

示例 1:

输入: 1->2

输出: false

示例 2:

输入: 1->2->2->1

输出: true

进阶：

你能否用 O (n) 时间复杂度和 O (1) 空间复杂度解决此题？

思路

把链表从中间分成两部分，即找到中间节点
对中间节点之后的链表进行反转
前半部分和后半部分反转后的链表进行值的比较

注意：分开前半部分的时候，前半部分的最后一个节点的 next 需要指向 None

时间复杂度：O(n)
空间复杂度：O(1)

测试用例

  • 空链表
  • 回文链表
    • 偶数个：1->2->3->3->2->1
    • 奇数个：1->2->3->2->1
  • 非回文链表
    • 1->2->3

      程序

      ```python

      Definition for singly-linked list.

      class ListNode:

      def init(self, x):

      self.val = x

      self.next = None

class Solution: def isPalindrome(self, head: ListNode) -> bool: if not head: return True dummy = ListNode(0) dummy.next = head

  1.     # 找到中间节点
  2.     low = dummy
  3.     fast = dummy
  4.     while fast and fast.next:
  5.         low = low.next
  6.         fast = fast.next.next
  7.     mid = low.next
  8.     # 对中间节点之后的节点反转
  9.     mid = self.reverse(mid)
  10.     # 断开前半部分
  11.     low.next = None 
  12.     # 对两个链表进行比较
  13.     cur = dummy.next
  14.     while mid and cur:
  15.         if mid.val != cur.val:
  16.             return False
  17.         mid = mid.next
  18.         cur = cur.next
  19.     return True
  21. # 对一个链表进行反转
  22. def reverse(self, head: ListNode) -> ListNode:
  23.     if not head:
  24.         return None
  25.     cur = None
  26.     while head:
  27.         node = head.next
  28.         head.next = cur
  29.         cur = head
  30.         head = node
  31.     return cur

```