好的，我们这次来详细讲解 LeetCode 第 234 题：回文链表（Palindrome Linked List）。

1. 题目描述

题目：给你一个单链表的头节点 head，请你判断该链表是否为回文链表。如果是，返回 true；否则，返回 false。

示例 1：
输入：head = [1,2,2,1]
输出：true

示例 2：
输入：head = [1,2]
输出：false

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

2. 题意理解

回文的意思是：一个序列正着读和反着读是一样的。
比如 [1, 2, 2, 1] 反过来还是 [1, 2, 2, 1]，所以是回文。

对于链表，我们不能像数组那样直接用下标从两头往中间比较，因为链表是单向的，只能从头到尾遍历。

难点：

• 单向链表不能直接反向比较。
• 如果要用 O(1) 额外空间，就不能把链表转成数组（那样是 O(n) 空间）。

3. 思路演进

思路 1：转成数组，再用双指针（O(n) 时间，O(n) 空间）

这是最直观的方法：

1. 遍历链表，把每个节点的值存入数组。
2. 用两个指针，一个在数组开头，一个在数组结尾，向中间移动，比较值是否相等。
3. 如果全部相等，则是回文；否则不是。

优点：简单易懂。
缺点：需要 O(n) 额外空间，不满足进阶要求。

思路 2：递归模拟反向比较（O(n) 时间，O(n) 空间）

利用递归栈模拟反向遍历，同时维护一个正向指针：

• 递归到链表末尾，然后返回时比较当前节点与正向指针的值，然后正向指针后移。

缺点：递归深度为 n，空间复杂度 O(n)，也不满足 O(1) 空间。

思路 3：快慢指针 + 反转后半部分（O(n) 时间，O(1) 空间）

这是满足进阶要求的标准解法，我们详细讲解。

4. 最优解法步骤详解（快慢指针 + 反转后半链表）

步骤 1：找到链表的中间节点

使用快慢指针：

• 慢指针 slow 每次走 1 步
• 快指针 fast 每次走 2 步

当快指针走到末尾时，慢指针就在中间（或中间偏左，取决于链表长度奇偶）。

示例：
链表 1 -> 2 -> 2 -> 1
初始：slow = 1, fast = 1
第 1 步：slow = 2, fast = 2
第 2 步：slow = 2, fast = 1（fast.next=null 停止）
此时 slow 在第二个 2，即后半部分的开头。

链表 1 -> 2 -> 3 -> 2 -> 1（奇数长度）
第 1 步：slow=2, fast=3
第 2 步：slow=3, fast=1（fast.next=null 停止）
此时 slow 在正中间 3，后半部分从 3 开始，但回文比较时中间节点可忽略。

步骤 2：反转后半部分链表

从 slow 位置开始，反转后面的链表。

反转链表的方法（迭代）：

prev = null
curr = slow
while curr:
    next_temp = curr.next
    curr.next = prev
    prev = curr
    curr = next_temp

反转后，prev 是反转后的新头。

示例：
1 -> 2 -> 2 -> 1
后半部分 2 -> 1 反转为 1 -> 2，同时第二个 2 的 next 指向 null。

步骤 3：比较前半部分和反转后的后半部分

用两个指针：

• p1 从原链表头开始
• p2 从反转后的后半部分的头开始

依次比较值，如果全部相等，则是回文。

注意：如果链表长度是奇数，后半部分会比前半部分短 1 个节点（中间节点不参与比较），所以只要 p2 不为空就继续比较，p2 先结束是正常的。

步骤 4（可选）：恢复链表

题目只要求判断回文，不要求保持原链表结构。但如果是面试，可以问面试官是否需要恢复。恢复的方法就是再次反转后半部分，接回前半部分。

5. 边界情况

• 空链表：直接返回 true（空链表是回文）
• 单节点链表：直接返回 true
• 双节点链表：如 1->2，比较 1 和 2，不相等则 false

6. 代码实现（Python）

def isPalindrome(head):
    if not head or not head.next:
        return True
    
    # 步骤 1：快慢指针找中点
    slow, fast = head, head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    
    # 步骤 2：反转后半部分
    prev = None
    curr = slow
    while curr:
        next_temp = curr.next
        curr.next = prev
        prev = curr
        curr = next_temp
    
    # 步骤 3：比较前后两半
    p1, p2 = head, prev
    while p2:  # 只要后半部分还没比完
        if p1.val != p2.val:
            return False
        p1 = p1.next
        p2 = p2.next
    
    # 步骤 4（可选）：恢复链表（此处省略）
    return True

7. 复杂度分析

• 时间复杂度：O(n)
  找中点 O(n/2)，反转 O(n/2)，比较 O(n/2)，总计 O(n)。
• 空间复杂度：O(1)
  只用了几个指针变量。

8. 总结

这道题的关键技巧：

1. 快慢指针找链表中点
2. 反转链表
3. 同时遍历比较

这样就在 O(1) 额外空间内完成了单向链表的回文判断。