专题 05链表：指针操作的艺术

5.1链表题考的是指针操作，不是算法

先说一个反直觉的事实：链表专题里几乎没有「需要灵光一现」的算法，难的都在细心上。 为什么？因为链表的本质就是「一串靠指针串起来的节点」，它没有任何随机访问能力—— 你想访问第 5 个节点，唯一的办法是从头走 5 步。这种结构决定了链表的题，难点永远是：

• 断链：改指针的时候，把下一步要用的引用弄丢了；
• 丢引用：没保存好下一个节点的位置，接不回去了；
• 边界：头节点要删、空链表、只有一个节点，这些「特殊情形」最容易漏。

链表和数组，差在哪

数组在内存里是一整块连续空间，每个元素紧挨着，CPU 知道第 i 个在哪（首地址 + i × 元素大小），所以按下标访问是 O(1)。 链表反过来，节点散落在内存各处，每个节点自己记着「下一个节点在哪」。

数组（连续内存，下标访问 O(1)）：
  ┌───┬───┬───┬───┬───┐
  │ 3 │ 7 │ 1 │ 9 │ 2 │      地址 1000,1004,1008,1012,1016
  └───┴───┴───┴───┴───┘
  缺点：中间插入/删除，后面元素要整体搬家（O(n)）。

链表（节点散落，靠指针串）：
  3 ──▶ 7 ──▶ 1 ──▶ 9 ──▶ 2 ──▶ null
  │       │       │       │
  ▼       ▼       ▼       ▼
addrA   addrB   addrC   addrD
  优点：删掉 1，只要让 7.next 指向 9，零搬家（O(1)）。

  代价：想找第 4 个？从 3 开始一步步 next，没有捷径。
        而且每个节点额外多存一个指针，占内存。

这一对比就清楚了：数组擅长「按位置找」，链表擅长「中途插拔」。 链表的题，本质都是「怎么安全地改指针，既不丢后面的链，又能把新链接上」。

5.2虚拟头节点：链表第一技巧

链表题里最烦的一种情况：头节点也可能被删除或改变。 比如要删掉所有值为 1 的节点，万一第一个节点就是 1，你「没有前一个节点」可以改它的 next， 只能特殊处理 head = head.next。每个边界都写 if，代码又丑又容易漏。

解法非常优雅：在真正的头节点前面，凭空造一个「虚拟头节点」（dummy），让它指向真正的头。 这样「真正的头」就降级成了「dummy 的下一个」，所有节点都有了「前一个」，处理完全统一。

原链表：       1 ──▶ 2 ──▶ 3 ──▶ null
要删头节点 1？  没「前一个」可改，得特殊处理。

加 dummy 后：
  dummy ──▶ 1 ──▶ 2 ──▶ 3 ──▶ null
    ▲
  哨兵：它不存真实数据，只负责「统一边界」
  所有删除都变成：改「前一个节点」的 next
  遍历从 dummy 出发，最后返回 dummy.next 就是新头

记住 dummy 的三条纪律，本章后面几乎每题都用：

• dummy 的 next 指向原 head（或构造时直接 new ListNode(-1, head)）；
• 用一个工作指针 cur 从 dummy 开始往后走，别直接动 dummy；
• 返回的是 dummy.next，不是 head——因为头可能已经被换掉了。

5.3移除链表元素（简单，力扣 203）

简单 核心：dummy 统一删除边界

题意：给你一个链表和一个值 val，删掉所有值等于 val 的节点，返回新链表头。 例：1→2→6→3→4→5→6，val=6 → 1→2→3→4→5。 注意 6 可能出现在中间，也可能出现在头（第一个就是 6）。

思路推导

最笨的想法：从头走到尾，遇到等于 val 的删掉。但删节点要改「它的前一个」的 next， 而头节点没有前一个——这就是 5.2 说的边界麻烦。

所以直接上 dummy：造一个哨兵指向 head，让 cur 从 dummy 出发。 关键判断是看 cur.next（而不是 cur 本身）：

• 如果 cur.next.val == val：要删的就是 cur.next，直接 cur.next = cur.next.next，把中间那个「跳过去」；
• 否则：cur 往前走一步 cur = cur.next。

为什么看 cur.next 而不是 cur？因为我们删节点靠的是「前一个节点的 next」， cur 就扮演「前一个」的角色。这样头节点被删时，是 dummy 的 next 被改，完全不用特判。

参考代码

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode dummy = new ListNode(-1, head); // 哨兵指向真正的头
        ListNode cur = dummy;                       // cur 扮演「前一个」
        while (cur.next != null) {                  // 只要还有「下一个」就检查
            if (cur.next.val == val) {
                cur.next = cur.next.next;          // 跳过要删的节点（断链重接）
            } else {
                cur = cur.next;                     // 没命中才前进
            }
        }
        return dummy.next;                          // 注意：返回 dummy.next
    }
}

复杂度

时间 O(n)：每个节点最多被访问一次。空间 O(1)：只用 dummy 和工作指针。 为什么是这个复杂度？无论删不删，每个节点都只被 cur 扫描一遍，没有回退。

手推一遍：1→2→6→3 删 6

光看代码不够，在纸上让指针走一遍才真懂。初始 dummy→1→2→6→3→null，cur=dummy：

cur=dummy: cur.next=dummy.next=1, val=1≠6 → cur 前进到 1
cur=1:     cur.next=2, val=2≠6 → cur 前进到 2
cur=2:     cur.next=6, val=6==6 → cur.next = 6.next = 3
          链变成 dummy→1→2→3→null（6 被跳过，断链重接成功）
cur=2:     cur.next=3, val=3≠6 → cur 前进到 3
cur=3:     cur.next=null, 循环条件 cur.next!=null 不成立 → 结束
返回 dummy.next = 1，即 1→2→3 ✓

注意第 3 步：cur 没有前进，因为它改完 cur.next 后，新的 cur.next 还得检查（万一后面还连着等于 6 的）。 这一题里连续删多个相同值也不会漏，正是因为这个「原地不前进」的写法。

5.4反转链表（简单，力扣 206）

简单 核心：prev / cur / next 三指针

题意：把 1→2→3→4→5 反转成 5→4→3→2→1，返回新头。 这是面试出现率极高的一道题，几乎是「链表指针操作」的入场券。

思路推导

反转的本质是：把每个节点原本指向下一个的箭头，调头指向前一个。 问题来了——当你把 cur.next 改成 cur.next = prev 之后，原来 cur 后面的链就找不到了， 因为你覆盖了 cur.next。所以操作前必须先把「下一个」存起来。

于是诞生三指针经典套路：

• prev：已经反转好的那一段的头（初始为 null，因为最前面没有）；
• cur：当前正在处理的节点；
• next：临时保存 cur.next，防止改箭头后丢失后面的链。

每一步只做四件事：① 存 next；② 让 cur 指向 prev；③ prev 前进到 cur；④ cur 前进到 next。 循环结束（cur 走到 null）时，prev 正好停在最后一个节点，也就是新头。

初始：   prev = null    cur = 1 ──▶ 2 ──▶ 3 ──▶ null

第1步：  next = 2
         1.next = null         （cur 指向 prev）
         prev = 1,  cur = 2
         →  1 ──▶ null      prev=1     cur=2 ──▶ 3 ──▶ null

第2步：  next = 3
         2.next = 1
         prev = 2,  cur = 3
         →  2 ──▶ 1 ──▶ null   prev=2    cur=3 ──▶ null

第3步：  next = null
         3.next = 2
         prev = 3,  cur = null
         →  3 ──▶ 2 ──▶ 1 ──▶ null   cur=null 结束

返回 prev = 3（新头）

参考代码（迭代版）

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;     // 已反转段的头，初始无
        ListNode cur = head;      // 当前节点
        while (cur != null) {
            ListNode next = cur.next; // ① 先存下一个，防断链
            cur.next = prev;          // ② 调头指向前一个
            prev = cur;               // ③ prev 前移
            cur = next;               // ④ cur 前移
        }
        return prev;             // prev 停在最后，即新头
    }
}

参考代码（递归版，思路更简洁）

递归的直觉：先一路递归到尾节点，让尾节点当新头；回退时把箭头一个个反调。 reverseList(head.next) 返回的是「以 head.next 为起点的子链反转后的新头」。 回到 head 这一层时，head.next 已经是反转后子链的尾节点，让 head.next.next = head 把它接回头， 再断开 head.next = null 即可。

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head; // 空或单节点直接返回
        ListNode newHead = reverseList(head.next); // 递归到尾，拿到新头
        head.next.next = head;  // 让后一个节点指向自己（反调箭头）
        head.next = null;       // 断开原来指向下一个的箭头
        return newHead;         // 一路把新头传上去
    }
}

复杂度

迭代与递归都是 O(n) 时间、O(1) 额外空间（递归版有 O(n) 调用栈，但逻辑清晰）。 为什么迭代是 O(1) 空间？全程只多了 prev/cur/next 三个指针，没有额外数组。

5.5合并两个有序链表（简单，力扣 21）

简单 核心：双指针 + dummy 串新链

题意：两个各自升序的链表，合成一个升序链表。 例：1→2→4 和 1→3→4 → 1→1→2→3→4→4。

思路推导

你脑子里怎么合并两个有序数组？每次比较两个队首最小的，取走，指针后移。链表一模一样， 只是「取走」变成「把那个节点接在新链后面」。

怎么串新链？还是用 dummy：让 cur 从 dummy 出发，每次比较 l1.val 和 l2.val， 小的那个接到 cur.next，对应的指针 (l1 或 l2) 后移，cur 也后移。 当某一个走完后，把另一个剩余的整段直接接上（剩下的本来就有序）。

l1: 1 ──▶ 2 ──▶ 4 ──▶ null
l2: 1 ──▶ 3 ──▶ 4 ──▶ null

dummy ──▶ (接 1 from l1) ──▶ (接 1 from l2) ──▶ (接 2) ──▶ (接 3) ...
cur 始终指向「新链最后一个」
最后 l1 或 l2 有一个剩一堆，cur.next 直接指向它。

参考代码

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(-1); // 新链哨兵
        ListNode cur = dummy;
        while (l1 != null && l2 != null) {  // 两个都还有才比
            if (l1.val <= l2.val) {
                cur.next = l1;              // 接 l1 当前节点
                l1 = l1.next;               // l1 前进
            } else {
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;                 // 新链尾前进
        }
        cur.next = (l1 != null) ? l1 : l2;  // 接上剩余整段
        return dummy.next;
    }
}

复杂度

时间 O(n+m)：每个节点最多被比较接一次。空间 O(1)（迭代）；递归版 O(n+m) 栈。 为什么接剩余整段是对的？因为另一个链表已经走完，剩下的部分天然有序且都比已接的大。

5.6环形链表 I / II（简单 / 中等，力扣 141 / 142）

简单 中等 核心：快慢指针 + 相遇数学

题意：

• I（141）：判断链表有没有环。例：3→2→0→-4，其中 -4 又指向 2 → 有环，返回 true。
• II（142）：不仅有环，还要返回环的入口节点。例：返回值为节点 2。

思路推导（I）：快慢指针

怎么判断「有没有环」而不用一个超大的计数器？经典招数是快慢指针（龟兔赛跑）： 慢指针每次走 1 步，快指针每次走 2 步。如果没环，快指针先到 null；如果有环， 快指针会在环里绕圈，最终从后面追上慢指针（相遇）。为什么一定追上？ 因为每走一轮，快的比慢的多走 1 步，环是有限的，差距迟早补平，就像操场上快的人套圈慢的人。

参考代码（I）

public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) { // 快指针走两步，要确认下下个存在
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) return true;  // 套圈相遇，必有环
        }
        return false;
    }
}

思路推导（II）：相遇后怎么找入口

这是本题的精华，也是很多人「背下代码但不懂」的地方。先定义几段距离：

• a：头节点到环入口的距离；
• b：环入口到快慢指针相遇点的距离（沿前进方向）；
• c：相遇点再走回环入口的距离。于是一圈长度 = b + c。

相遇时，慢指针走了 a + b；快指针走的是 a + b 再多绕了 n 圈，即 a + b + n×(b+c)。 快指针速度是慢的两倍，所以路程也是两倍：

2 × (a + b) = a + b + n × (b + c)
        a + b = n × (b + c)
            a = n × (b + c) − b
            a = (n − 1) × (b + c) + c
            a = c + (n − 1) 圈

直觉翻译：「从头到入口的距离 a」等于「从相遇点沿环走回入口的距离 c」加上整数圈。 也就是说——如果你让一个指针从头节点出发、另一个从相遇点出发， 两者都以每步 1 的速度前进，那么从相遇点出发的那个，走完 c 就到入口，而此时从头出发的正好也走到入口（它走 a = c + 整圈）。 它们必然在入口节点相遇。这就是 II 的解法：相遇后，一个回头部，同步走，再相遇即入口。

参考代码（II）

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {            // 先找到相遇点
                ListNode p = head;         // 一个指针拉回头部
                while (p != slow) {        // 同速走，必在入口相遇
                    p = p.next;
                    slow = slow.next;
                }
                return p;                  // 入口节点
            }
        }
        return null;                       // 无环
    }
}

复杂度

时间 O(n)：快慢指针最多绕一圈多就相遇，找入口再走 a 步，合起来线性。 空间 O(1)：只用了几个指针。为什么快指针设 2 步、慢设 1 步？步数差 1 保证「每轮差距 +1」，必然套圈； 设更大的倍数也行但没必要，且可能跳过。

5.7删除链表的倒数第 N 个结点（中等，力扣 19）

中等 核心：快慢指针定距

题意：删掉倒数第 N 个节点。例：1→2→3→4→5，n=2 → 1→2→3→5。 注意 n 保证有效，且可能删的就是头节点（n 等于长度）。

思路推导

链表不能倒着数，但我们可以「换算」：倒数第 N 个 = 正数第 (长度 − N + 1) 个。 直接数长度再走第二趟当然可以，但一趟搞定更优雅——用快慢指针制造固定间距。

让快指针先走 N 步，此时快慢之间正好隔了 N 个节点。然后快慢一起走， 当快指针到达末尾（null）时，慢指针正好停在「倒数第 N+1 个」，也就是待删节点的前一个。 一个 slow.next = slow.next.next 就删掉了。

这里有个边界：如果要删的是头节点，慢指针一开始就得有「前一个」可站——所以还是请出 dummy。

链表 1→2→3→4→5，删倒数第 2（即 4）
dummy→1→2→3→4→5→null
fast 先走 n+1=3 步：fast 指向 3
slow 仍在 dummy
然后同走，直到 fast=null：
  fast 走完 3→4→5→null，共 3 步
  slow 走 dummy→1→2→3
slow 停在 3（待删节点 4 的前一个），slow.next = slow.next.next 删掉 4

注意这里 fast 先走的是 n + 1 步（不是 n 步），因为我们要让 slow 停在「前一个」， 多走一步就是为了留出一个身位。

参考代码

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(-1, head); // 处理删头节点
        ListNode fast = dummy, slow = dummy;
        for (int i = 0; i < n + 1; i++) {         // 快指针先走 n+1 步
            fast = fast.next;
        }
        while (fast != null) {                    // 同速走，直到快指针到尾
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;               // 删掉倒数第 n 个
        return dummy.next;
    }
}

复杂度

时间 O(n)：fast 走完一趟，slow 跟着走，没有回退。空间 O(1)。 为什么先走 n+1 而不是 n？因为目标是让 slow 停在待删节点的前一个， n+1 的间距恰好让 fast 到 null 时 slow 落在前一个。

5.8本专题常见坑

5.9自测题