Hot 100 --- 回文链表

本文概览：本文以LeetCode经典题目"回文链表"为例，从暴力解法入手，先讲解反转链表的核心原理，再引出快慢指针找中点+反转后半段的 O(1) 空间解法

一、题目

回文链表题目

二、题目分析

给定一个单链表的头节点 head，判断该链表是否为回文链表

目标：判断链表是否从前向后读和从后向前读完全相同

核心难点：链表不像数组那样可以随机访问，无法直接从尾部向前遍历

思路概览

Java实现代码如下

public boolean isPalindrome(ListNode head) {
    // 快指针
    ListNode fast = head;
    // 慢指针
    ListNode slow = head;
    // 快慢指针同时移动，快指针每次移动两步，慢指针每次移动一步
    // 当快指针到达链表末尾时，慢指针正好到达链表的中间位置
    while (fast.next != null && fast.next.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    // 将链表从慢指针开始反转，得到反转后的后半段链表的头节点
    ListNode secondHalf = reverseList(slow.next);
    // 判断链表是否为回文链表
    while (secondHalf != null) {
        if (secondHalf.val != head.val) {
            return false;
        }
        secondHalf = secondHalf.next;
        head = head.next;
    }
    return true;
}

private ListNode reverseList(ListNode head) {
    // 记录新链表的头节点（已反转的部分）
    ListNode prev = null;
    // 记录当前正在处理的节点
    ListNode curr = head;
    while (curr != null) {
        // 记录当前节点的下一个节点，防止断链后丢失后续节点
        ListNode temp = curr.next;
        // 将当前节点的 next 指针指向 prev，完成反转
        curr.next = prev;
        // 新头节点前移
        prev = curr;
        // 移动到下一个待处理节点
        curr = temp;
    }
    return prev;
}

思路简要说明

快慢指针找中点：快指针每次走两步，慢指针每次走一步。快指针到达末尾时，慢指针恰好在中点
反转后半段链表：从慢指针的下一个节点开始反转后半段链表
前后两段比较：前半段从头节点开始，后半段从反转后的头节点开始，逐个比较节点值

三、思路详解

暴力解法入手

问题分析

判断回文的核心是"正着读和倒着读一样"。对于数组，直接从两端向中间比较就行；但对于链表，由于它只能单向遍历，无法从尾部向前访问

所以最自然的想法是：先遍历一遍链表，把所有值存到一个列表中，然后像数组一样从两端向中间比较

链表：1 → 2 → 3 → 2 → 1
      ↓
    遍历存储
      ↓
列表：[1, 2, 3, 2, 1]
      ↓
    双指针比较：
    left=0, right=4: 1==1 ✓
    left=1, right=3: 2==2 ✓
    left=2, right=2: 3==3 ✓

这个思路完全可行，但有明显的缺陷：

时间复杂度：O(n)，遍历一次链表 + 遍历一次列表
空间复杂度：O(n)，需要额外存储 n 个节点的值
核心瓶颈：需要遍历两次（链表 → 列表 → 比较），且空间开销为 O(n)

能不能不用额外空间？

链表的最大特点是：每个节点只有 next 指针指向下一个节点，没有 prev 指针指向前一个。如果能让链表"倒过来"，即从尾部也能访问，那就和数组一样了

这就引出了两个问题需要解决：

如何找到链表的中间节点？（我们需要把链表分成前后两半）
如何反转链表？（让后半段链表"倒过来"，就可以从后往前读了）

子问题一：反转链表

链表反转的核心是改变每个节点的 next 指向，让它指向前一个节点而不是后一个节点。这样链表就从 1→2→3 变成了 3→2→1

我们需要三个指针配合：

prev：已反转部分的头节点（初始为 null，因为反转后的链表尾部指向 null）
curr：当前正在处理的节点
temp：临时保存 curr.next，防止断链后丢失后续节点

每轮循环的四步操作：

temp = curr.next：先保存下一个节点，不然断链后就找不到了
curr.next = prev：将当前节点的 next 指向前一个节点，完成反转
prev = curr：新头节点前移，已反转部分延长
curr = temp：移动到下一个待处理节点

图示说明

以 1 → 2 → 3 为例，对应代码如下：

ListNode prev = null;   // 已反转部分的头节点，初始为null
ListNode curr = head;   // 当前正在处理的节点，从链表头开始
while (curr != null) {  // 当还有节点未处理时继续
    ListNode temp = curr.next;  // ① 保存下一个节点，防止断链后丢失
    curr.next = prev;           // ② 将当前节点的next指向前一个节点（已反转部分）
    prev = curr;                // ③ 新头节点前移，当前节点加入已反转部分
    curr = temp;                // ④ 移动到下一个待处理节点
}
return prev;  // prev最终指向反转后链表的头节点

初始状态：

prev = null, curr = 1, temp = ?

null ← 1 → 2 → 3
       ↑
      curr

第1轮（处理节点 1）：

temp = curr.next = 2    // ① 保存2，防止等下断链后找不到了
curr.next = prev = null // ② 1的next指向null（反转完成）
prev = curr = 1         // ③ prev前移，已反转部分是：1→null
curr = temp = 2         // ④ curr移到下一位

null ← 1    2 → 3
       ↑    ↑
      prev curr

第2轮（处理节点 2）：

temp = curr.next = 3    // ① 保存3
curr.next = prev = 1    // ② 2的next指向1（反转完成）
prev = curr = 2         // ③ prev前移，已反转部分是：2→1→null
curr = temp = 3         // ④ curr移到下一位

null ← 1 ← 2    3
            ↑    ↑
           prev curr

第3轮（处理节点 3）：

temp = curr.next = null // ① 保存null（已经是末尾了）
curr.next = prev = 2    // ② 3的next指向2（反转完成）
prev = curr = 3         // ③ prev前移，已反转部分是：3→2→1→null
curr = temp = null      // ④ curr=null，循环结束

null ← 1 ← 2 ← 3
                 ↑
                prev

循环结束，prev 就是反转后链表的头节点，返回 prev

子问题二：快慢指针找中点

反转链表解决了"如何让链表倒过来"的问题，但还有一个问题：我们不知道链表有多长，怎么知道从哪个位置开始反转？

这就需要找到链表的中间节点。如果只遍历一次，那只能遍历到末尾才知道长度；如果遍历两次，那效率又降低了

一个巧妙的技巧是——快慢指针：

fast 指针每次走两步
slow 指针每次走一步

当 fast 走到链表末尾时，slow 恰好走到链表中间。这就像两个人跑步，一个速度是另一个的两倍，当快的跑到终点时，慢的正好跑了一半

奇偶长度的不同情况

快慢指针的循环条件是 while (fast.next != null && fast.next.next != null)，为什么这样写？因为这可以正确处理奇数和偶数两种情况：

奇数长度（如 1 → 2 → 3 → 2 → 1，共5个节点）：

轮次	fast	slow
初始	1	1
1	fast = fast.next.next = 3	slow = slow.next = 2
2	fast = fast.next.next = null（末尾）	slow = slow.next = 3

此时 fast 停在最后一个节点的 next（即 null），slow 恰好停在正中间的节点 3。后半段从 slow.next 开始，即 2 → 1

偶数长度（如 1 → 2 → 2 → 1，共4个节点）：

轮次	fast	slow
初始	1	1
1	fast = fast.next.next = 2（第二个2）	slow = slow.next = 2（第一个2）
2	fast.next = null（fast在倒数第二个节点，fast.next.next会越界）	循环停止

此时 fast 停在倒数第二个节点（第二个 2），slow 停在前半段的最后一个节点（第一个 2）。后半段从 slow.next 开始，即 2 → 1

总结：

奇数长度：slow 停在正中间节点，后半段比前半段少一个节点（少中间那个）
偶数长度：slow 停在前半段的最后一个节点，前后两段长度相等

回文链表优化解法

整体思路

既然链表不能从后往前读，那我们就利用上面两个技巧：

用快慢指针找到链表中点
将后半段链表反转，这样后半段就可以从前往后读了（相当于从原链表的尾部往前读）
前半段和反转后的后半段逐个比较，如果完全相同就是回文

原链表：1 → 2 → 3 → 2 → 1
              ↑
            slow指向3（中点）

后半段反转前：2 → 1
后半段反转后：1 → 2

比较：前半段 1→2→3，后半段 1→2
     1==1 ✓, 2==2 ✓, 后半段结束 ✓

为什么这样不会出错？

快慢指针找中点时，循环条件是 fast.next != null && fast.next.next != null，这保证了：

对于偶数长度链表，fast 停在倒数第二个节点，slow 停在前半段最后一个节点
对于奇数长度链表，fast 停在最后一个节点，slow 停在正中间节点

这样 slow.next 始终是后半段的起始位置，反转后得到的是完整的后半段

具体步骤：

快慢指针找中点：
- 快指针 fast 每次走两步，slow 每次走一步
- 当 fast 到达链表末尾时，slow 恰好在中点
- 对于奇数长度链表（如 1→2→3→2→1），slow 指向正中间的节点 3，后半段从 slow.next 开始
- 对于偶数长度链表（如 1→2→2→1），slow 指向前半段的最后一个节点 2（第一个 2），后半段从 slow.next 开始
反转后半段：从 slow.next 开始反转后半段链表
前后两段比较：前半段从 head 开始，后半段从反转后的头节点开始，逐个比较节点值

举例说明

以 1 → 2 → 3 → 2 → 1 为例（奇数长度）

第一步：快慢指针找中点

轮次	fast	slow
初始	1	1
1	3	2
2	末尾(null)	3

slow 指向节点 3，slow.next 指向节点 2（后半段第一个）

第二步：反转后半段

后半段：2 → 1 → 反转后 → 1 → 2

第三步：比较

步骤	前半段(head)	后半段(secondHalf)	比较
1	1	1	相等
2	2	2	相等
3	3	null	后半段结束，前半段还剩中间节点，不影响

最终返回 true

以 1 → 2 → 2 → 1 为例（偶数长度）