06 链表双指针实战：倒数第 N 个节点、相交链表与回文链表

链表双指针实战：倒数第 N 个节点、相交链表与回文链表

摘要

链表双指针的核心技巧可以归纳为两类：距离双指针（一个指针先走 K 步，然后两个指针同速移动，利用固定距离差获取信息）和等长对齐（使两个不等长的链表在对齐位置上同步移动）。本文通过三道经典题——删除倒数第 N 个节点、相交链表、回文链表——完整展示这两类技巧，并深入剖析哑节点（Dummy Node）的工程价值。

---

第 1 章 距离双指针：找倒数第 K 个节点

1.1 核心技巧

“链表中倒数第 $K$ 个节点”等价于”从头节点出发，第 $n-K+1$ 个节点”（$n$ 是链表长度）。但链表不支持随机访问，不能像数组一样直接用 nums[n-K]。

如果先遍历一次获取长度 $n$，再从头走 $n-K$ 步，需要两次遍历。能否只遍历一次？

距离双指针的思路：

设两个指针 fast 和 slow，让 fast 先走 $K$ 步，然后 fast 和 slow 同时以速度 1 移动。当 fast 到达链表末尾（null）时，slow 恰好在倒数第 $K$ 个节点。

为什么？

当 fast 先走了 $K$ 步，fast 和 slow 之间的距离固定为 $K$。此后两者同步移动，距离保持不变。当 fast 到达末尾（走了 $n$ 步）时，slow 走了 $n-K$ 步，即从头节点起第 $n-K+1$ 个节点，也就是倒数第 $K$ 个节点。

---

第 2 章 LeetCode 19：删除链表的倒数第 N 个节点

2.1 题目

LeetCode 19 - Remove Nth Node From End of List（中等）

给你一个链表，删除链表的倒数第 n 个节点，并且返回链表的头节点。

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

输入：head = [1], n = 1
输出：[]

输入：head = [1,2], n = 1
输出：[1]

2.2 为什么需要哑节点（Dummy Node）

直接操作链表节点时，删除操作需要找到被删除节点的前驱节点（prev），然后执行 prev.next = prev.next.next。

问题：如果被删除的是头节点（倒数第 $n$ 个节点恰好是第一个节点），头节点没有前驱，代码需要特殊处理 return head.next。

哑节点（Dummy Node）：在头节点之前插入一个虚拟节点 dummy，dummy.next = head。这样，所有节点（包括原来的头节点）都有前驱节点（dummy 是原头节点的前驱）。删除操作统一为 prev.next = prev.next.next，不需要特殊处理头节点。

核心概念：哑节点的工程价值

哑节点是链表操作中消除”头节点特殊情况”的标准技巧。几乎所有涉及”可能删除头节点”或”在头节点前插入”的链表题，第一步都应该创建哑节点。它的代价是 $O(1)$ 的额外空间，换来的是代码的统一性和正确性。

2.3 完整解法

public ListNode removeNthFromEnd(ListNode head, int n) {
    // 创建哑节点，统一头节点操作
    ListNode dummy = new ListNode(0);
    dummy.next = head;
 
    ListNode fast = dummy, slow = dummy;
 
    // fast 先走 n+1 步（不是 n 步）
    // 为什么是 n+1 步？因为我们要找"被删节点的前驱"，而不是"被删节点本身"
    for (int i = 0; i < n + 1; i++) {
        fast = fast.next;
    }
 
    // fast 和 slow 同速移动，直到 fast 为 null
    while (fast != null) {
        slow = slow.next;
        fast = fast.next;
    }
 
    // 此时 slow 是被删节点的前驱
    slow.next = slow.next.next;
 
    return dummy.next;
}

2.4 “先走 n+1 步”的推导

要删除倒数第 $n$ 个节点，需要找到它的前驱（倒数第 $n+1$ 个节点）。

用距离双指针找”倒数第 $n+1$ 个节点”，需要 fast 先走 $n+1$ 步，然后 fast 走到 null 时，slow 在倒数第 $n+1$ 个节点。

从 dummy 出发：fast 从 dummy 出发先走 $n+1$ 步，此时 fast 在原链表的第 $n$ 个节点处（因为 dummy 是第 0 个”节点”）。

不，让我们重新数一下：

设链表有 $L$ 个节点（不含 dummy）。

• fast 从 dummy 先走 $n+1$ 步，fast 指向原链表第 $n$ 个节点（0-indexed：dummy=0, head=1, ...，所以 $n+1$ 步后在节点 $n+1$，即原链表从 0 开始的第 $n$ 个节点）。
• 然后两者同速移动，当 fast == null（即 fast 走到 $L+1$ 位置，超出链表末尾）时，slow 在位置 $L+1-(n+1)=L-n$（即倒数第 $n+1$ 个节点）。

slow 在倒数第 $n+1$ 个节点，即被删节点的前驱，执行 slow.next = slow.next.next 删除被删节点。正确。

2.5 边界条件

删除头节点（n 等于链表长度）：

fast 先走 $n+1$ 步后，fast = null（已经越过末尾）？不对，fast 从 dummy 出发，走 $n+1$ 步后恰好是链表最后一个节点（因为链表有 $n$ 个节点，dummy 出发走 $n+1$ 步到第 $n$ 个节点，再走一步到 null）。

等等，让我们用例子验证：链表 [1, 2, 3]（长度 3），删除倒数第 3 个节点（即头节点 1）。

• dummy -> 1 -> 2 -> 3 -> null
• fast 先走 $3+1=4$ 步：dummy(0) → 1(1) → 2(2) → 3(3) → null(4)
• fast == null，退出”先走”循环
• while (fast != null) 不执行，slow 仍在 dummy
• slow.next = slow.next.next：dummy.next = dummy.next.next = 2，即删除头节点 1

使用哑节点后，删除头节点的情况被自然处理，无需特判。

---

第 3 章 LeetCode 160：相交链表

3.1 题目

LeetCode 160 - Intersection of Two Linked Lists（简单）

给你两个单链表的头节点 headA 和 headB，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null。

题目保证：整个链式结构中不存在环。

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：No intersection

3.2 两种解法思路

解法一：哈希表

遍历链表 A，将所有节点存入 HashSet。然后遍历链表 B，如果某个节点在 HashSet 中，则是交点。时间 $O(m+n)$，空间 $O(m)$。

解法二：等长对齐（双指针，空间 $O(1)$）

核心观察：如果两个链表相交，交点之后的部分是完全相同的（共享节点），交点之前的部分长度可能不同。

设链表 A 的非公共部分长度为 $a$，链表 B 的非公共部分长度为 $b$，公共部分长度为 $c$。

• A 的总长度：$a+c$
• B 的总长度：$b+c$

如果指针 pA 走完 A 后跳到 B 的头继续走，走了 $a+c+b$ 步到达交点。 如果指针 pB 走完 B 后跳到 A 的头继续走，走了 $b+c+a$ 步到达交点。

$a+c+b=b+c+a$，两者到达交点的步数相同！因此，两个指针会同时到达交点。

3.3 完整解法

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    ListNode pA = headA, pB = headB;
 
    // 两指针各自遍历，到末尾后跳到另一条链表的头
    while (pA != pB) {
        pA = (pA == null) ? headB : pA.next;
        pB = (pB == null) ? headA : pB.next;
    }
 
    // pA == pB，要么是交点，要么都是 null（无交点）
    return pA;
}

无交点时：两指针各走 $a+c+b=b+c+a$ 步后，同时到达 null（无公共部分时 $c=0$），pA == pB == null，返回 null。正确。

3.4 为什么判断 pA == null 而不是 pA.next == null？

如果用 pA.next == null，当 pA 到达最后一个节点时跳转，pA 在跳转前等于链表 A 的最后一个节点，跳转后 pA = headB。但此时 pA 已经是最后一个节点，还没有走到 null，逻辑会少走一步。

正确做法：pA == null 时跳转，即 pA 已经走出链表（在 null 位置），此时跳到另一条链表的头节点 headB。这样两指针走的步数是 $a+c+1（null）$ 和 $b+c+1（null）$，跳转后走 $b+c$ 和 $a+c$ 步到交点，合计步数相等。

---

第 4 章 LeetCode 234：回文链表

4.1 题目

LeetCode 234 - Palindrome Linked List（简单）

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

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

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

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

4.2 解题思路

回文链表的核心挑战：链表不支持随机访问，不能像数组一样直接用 left 和 right 指针比较两端。

朴素解法：将链表转为数组，然后用对撞指针判断回文。时间 $O(n)$，空间 $O(n)$。

$O(1)$ 空间解法：分三步：

1. 用快慢指针找链表中点
2. 反转后半段链表（原地操作，$O(1)$ 空间）
3. 比较前半段和反转后的后半段是否相同
4. （可选）恢复链表原始结构

4.3 完整解法

public boolean isPalindrome(ListNode head) {
    if (head == null || head.next == null) return true;
 
    // 步骤一：找链表中点
    ListNode slow = head, fast = head;
    while (fast.next != null && fast.next.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    // 循环结束后，slow 是前半段的最后一个节点
    // 奇数：[1,2,3,2,1] → slow = 3（中点）
    // 偶数：[1,2,2,1] → slow = 第一个 2
 
    // 步骤二：反转后半段
    ListNode secondHalfStart = reverseList(slow.next);
 
    // 步骤三：比较前半段和反转后的后半段
    ListNode p1 = head, p2 = secondHalfStart;
    boolean result = true;
    while (p2 != null) {
        if (p1.val != p2.val) {
            result = false;
            break;
        }
        p1 = p1.next;
        p2 = p2.next;
    }
 
    // 步骤四：恢复链表（可选，但工程上推荐）
    slow.next = reverseList(secondHalfStart);
 
    return result;
}
 
// 反转链表（迭代版本）
private ListNode reverseList(ListNode head) {
    ListNode prev = null, cur = head;
    while (cur != null) {
        ListNode next = cur.next;
        cur.next = prev;
        prev = cur;
        cur = next;
    }
    return prev;
}

4.4 找中点时循环条件的精确分析

注意步骤一使用的循环条件是 fast.next != null && fast.next.next != null，而不是前面 LeetCode 876 中的 fast != null && fast.next != null。

两者找到的中点不同：

while (fast != null && fast.next != null)（876 题的写法）：

• 奇数 [1,2,3,2,1]：slow=3（中点）
• 偶数 [1,2,2,1]：slow=第二个 2（后半段的第一个节点）

while (fast.next != null && fast.next.next != null)（234 题需要的写法）：

• 奇数 [1,2,3,2,1]：slow=3（中点）
• 偶数 [1,2,2,1]：slow=第一个 2（前半段的最后一个节点）

回文链表判断中，我们需要在 slow.next 处分割链表（slow 是前半段的最后一个节点，slow.next 是后半段的第一个节点）。所以需要用第二种写法，让 slow 停在前半段末尾，而不是后半段开头。

链表	876 写法 slow 位置	234 写法 slow 位置
[1,2,3,2,1]（奇数 5）	节点 3（中点）	节点 3（中点）
[1,2,2,1]（偶数 4）	第二个 2（后半段第一个）	第一个 2（前半段最后一个）
[1,2,3]（奇数 3）	节点 2（中点）	节点 2（前半段最后一个？）

对奇数长度链表 [1,2,3]，234 写法中 slow=2（第二个节点），slow.next=3（后半段），比较 1 和 3——显然不相等，但 [1,2,3] 确实不是回文，所以正确。

生产避坑：两种找中点写法的微妙差异

找中点有两种常用写法，停下来的位置差了一步（偶数长度时）。在用快慢指针找中点后紧接着操作链表（如分割、反转）时，必须搞清楚”slow 停在中点本身”还是”slow 停在中点的前驱”，选择对应的循环条件。选错会导致后续操作在错误位置分割链表。

4.5 为什么要恢复链表结构？

步骤四（恢复链表）在 LeetCode 上不影响判题，但在工程实践中非常重要：

1. 函数的语义契约：函数接受链表，不应该悄悄修改它（副作用）。调用方不会预期 isPalindrome 会改变链表结构。
2. 并发安全：多线程场景下，修改共享链表结构会导致竞态条件。
3. 可调试性：函数执行后链表被破坏，调试时难以复现原始状态。

---

第 5 章 链表双指针的通用技巧总结

5.1 哑节点的适用场景

场景	是否需要哑节点
可能删除头节点	需要
在头节点前插入	需要
合并两条链表（结果可能从任一链表开始）	通常需要
仅遍历或查询，不修改链表结构	不需要
只修改节点值，不修改 next 指针	不需要

5.2 三类链表双指针操作模式

模式一：距离双指针（先走 K 步）

• 用途：找倒数第 K 个节点
• 实现：fast 先走 K 步，然后两指针同速移动

模式二：等长对齐（跳转到另一条链表）

• 用途：找两条链表的交点
• 实现：走完本链表后跳到另一条链表头，两指针总步数相等

模式三：快慢指针（步幅不同）

• 用途：找中点、检测环、找环入口
• 实现：快指针每步 2，慢指针每步 1

5.3 面试中的”链表四连”

链表题的四个高频考点，每个都有对应的双指针技巧：

1. 环检测：快慢指针（Floyd 算法）→ LeetCode 141
2. 环入口：快慢相遇后重置一个到头，同速移动 → LeetCode 142
3. 倒数第 K 个：距离双指针（先走 K+1 步找前驱）→ LeetCode 19
4. 两链表交点：等长对齐（走完跳到另一条）→ LeetCode 160

掌握这四个技巧，链表双指针题基本全覆盖。

---

小结

本文通过三道题覆盖了链表双指针的两大核心变体：

• 距离双指针（LeetCode 19）：fast 先走 $n+1$ 步找倒数第 $n$ 个节点的前驱，配合哑节点统一处理头节点删除
• 等长对齐（LeetCode 160）：两指针各走 $a+c+b$ 步，同时到达交点或同时到达 null
• 快慢指针组合（LeetCode 234）：快慢指针找中点 + 反转后半段 + 对比两半 + 恢复结构

下一篇正式进入滑动窗口领域，从最基础的定长窗口和可变窗口出发，建立统一的”扩张-收缩”状态机框架。