​链表题解——回文链表【LeetCode】

 算法思路

1. 核心思想：

   • 找到链表的中间节点。
   • 反转链表的后半部分。
   • 比较链表的前半部分和反转后的后半部分，如果值完全一致，则是回文链表。

2. 具体步骤：

   • 使用快慢指针找到链表的中间节点（middleNode 方法）。
   • 反转链表的后半部分（reverseList 方法）。
   • 比较链表的前半部分和反转后的后半部分，如果所有节点的值都相等，则返回 True，否则返回 False。

3. 关键点：

   • 快慢指针找到中间节点的时间复杂度为 O(n)。
   • 反转链表的时间复杂度为 O(n)。
   • 比较链表的时间复杂度为 O(n)。
   • 总时间复杂度为 O(n)，空间复杂度为 O(1)

class ListNode:def __init__(self, x):self.val = x  # 初始化节点的值self.next = None  # 初始化节点的下一个节点为 Noneclass Solution:# 876. 链表的中间结点def middleNode(self, head):slow = fast = head  # 初始化慢指针和快指针，都指向链表头节点while fast and fast.next:  # 当快指针及其下一个节点不为空时slow = slow.next  # 慢指针每次移动一步fast = fast.next.next  # 快指针每次移动两步return slow  # 返回慢指针指向的节点（即链表的中间节点）# 206. 反转链表def reverseList(self, head):pre, cur = None, head  # 初始化前驱节点为 None，当前节点为链表头节点while cur:  # 当当前节点不为空时nxt = cur.next  # 保存当前节点的下一个节点cur.next = pre  # 将当前节点的 next 指向前驱节点pre = cur  # 前驱节点移动到当前节点cur = nxt  # 当前节点移动到下一个节点return pre  # 返回反转后的链表头节点def isPalindrome(self, head):mid = self.middleNode(head)  # 找到链表的中间节点head2 = self.reverseList(mid)  # 反转后半部分链表while head2:  # 遍历反转后的后半部分链表if head.val != head2.val:  # 如果前半部分和后半部分的节点值不相等return False  # 不是回文链表，返回 Falsehead = head.next  # 移动前半部分的指针head2 = head2.next  # 移动后半部分的指针return True  # 所有节点值都相等，是回文链表，返回 True