链表：指针操作的基本功

这一课你将能做到

1. 画出链表节点的指向关系，用「断链前先保存」的原则完成反转
2. 用快慢指针判断环并说出环入口的求法
3. 用哑节点（dummy）合并两个有序链表，理解它为什么能消掉分支

为什么要学

数组在内存里是一排连续座位，链表则是一串「各带地址条的节点」——每个节点存数据和下一个节点的引用，节点散落内存也没关系。插入、删除不需要搬动整排元素，O(1) 就能改指针完成。

链表在后端开发中直接写得不算多（各种容器类已经封装好），但 LRU 缓存（LinkedHashMap / 自定义双向链表）、跳表、消息队列的底层结构都离不开它。面试更现实的意义是：链表题是「指针纪律」的试金石——谁在断链前保存了后续节点、谁考虑了空指针，一眼可见。而且反转、判环、合并这三题几乎是必考清单，属于必须形成肌肉记忆的内容。

先建立图像

单链表节点定义（所有题目的公共前提）：

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

链表：   1 → 2 → 3 → null
反转后： 3 → 2 → 1 → null

判环：   3 → 4 → 5
         ↑       ↓
         7 ← 6 ←      ← fast 走两步、slow 走一步，必相遇

链表题三大纪律：

1. 断链前先存：改 next 指向前，先把原后继保存好，否则后半截链表直接丢失。
2. 凡是 x.next 必先确认 x 非 null。
3. 头节点可能变化时，用 dummy 占位，避免单独处理头节点的分支。

跟着做

步骤 1：LeetCode 206「反转链表」（简单）

给定单链表头节点，反转整条链并返回新头节点。

迭代思路用三个指针：prev（已反转部分的头）、curr（当前处理节点）、next（暂存原后继）。每个节点做同一个动作——把 next 指针从「指向后」改成「指向前」。

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next; // 1. 先存原后继（断链前先存）
            curr.next = prev;          // 2. 反转指向
            prev = curr;               // 3. prev 前进一步
            curr = next;               // 4. curr 前进一步
        }
        return prev; // curr 已为 null，prev 就是新头
    }
}

逐点讲：循环不变量——prev 是「已经反转好部分」的头，curr 是「尚未反转部分」的头。时间 O(n)，空间 O(1)。

递归写法（面试也常考推导）：

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）反过来指向自己
        head.next = null;      // 自己成为新尾，断开旧方向
        return newHead;
    }
}

递归时间 O(n)、空间 O(n)（调用栈）。建议先吃透迭代，递归用来展示理解深度。

步骤 2：LeetCode 141「环形链表」（简单）

判断链表中是否有环。

思路：快慢指针（Floyd 判圈）。slow 每轮走 1 步，fast 走 2 步；无环时 fast 先到 null；有环时 fast 会从后面套圈追上 slow，两者必然相遇。

class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                return true; // 同址相遇
            }
        }
        return false;
    }
}

逐点讲：while 条件保证 fast 还能安全走两步。时间 O(n)，空间 O(1)。

追问：环入口在哪（LeetCode 142）？相遇后把其中一个指针放回 head，然后两指针同速各走一步，再次相遇点就是入口。数学依据：设头到入口距离 a、入口到相遇点 b、相遇点回入口 c，相遇时 2(a+b)=a+b+k(b+c) 推出 a = (k-1)(b+c)+c，即从头走 a 步与从相遇点走 c 步（加整数圈）恰好同到入口。面试能口述这个关系即可。

步骤 3：LeetCode 21「合并两个有序链表」（简单）

两个升序链表合并为一个升序链表。

用 dummy 节点作为结果链的「假头」，再用一个 tail 指针始终指向结果链末尾；每次挑两个链表当前值更小的接在 tail 后。

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                tail.next = list1;
                list1 = list1.next;
            } else {
                tail.next = list2;
                list2 = list2.next;
            }
            tail = tail.next;
        }
        // 一方耗尽，另一方整条接上
        tail.next = (list1 != null) ? list1 : list2;
        return dummy.next;
    }
}

逐点讲：dummy 的价值是 tail 初始就有处可挂，结果链的真头是 dummy.next。最后剩余链表可以整条接，因为它本身已经有序。时间 O(n+m)，空间 O(1)。

讲清楚要点

1. 链表操作的本质是改指向，不是搬数据：一切复杂动作都可以拆成若干次 a.next = b。
2. 反转的四步动作对每个节点完全相同：存后继、指向前、双指针前进。能用循环不变量描述，就说明真懂了。
3. 快慢指针是链表的「雷达」：判环用 2 倍速；找中点同样用它（slow 停在中点），归并排序链表时就是这样切分。
4. dummy 节点消空头分支：凡是结果头不确定（合并、删除、分组），先挂 dummy 几乎不会错。
5. 画图永远比硬想快：链表 bug 90% 能靠三四个节点的手画图立刻定位。

你可能会懵的地方

• 反转时为什么 curr 最后是 null，返回的却是 prev？ 循环退出条件是 curr==null，说明所有节点都处理完了；最后处理的那个节点在退出前已赋给 prev，prev 正是原链最后一个节点、即新头。

• 快慢指针为什么在环里一定相遇，不会刚好错开吗？ 可以相对运动理解：fast 每轮比 slow 多走 1 步，在环里相对速度为 1，它会逐个缩小与 slow 的距离（按环内位置计），必然经过重合点，不会「跳过」。

• 合并时为什么能直接 tail.next = list1 接整条？ list1 剩余节点保持原有链接且整体有序，而 list2 已耗尽，不存在还要比较的对象，整链接入即完成排序。

• 递归反转的 head.next = null 不写会怎样？ 会在新链尾部留下指回前一节点的旧链接，形成局部小环，遍历到尾部时无限循环。

• 双向链表要注意什么？ 每个节点多一个 prev，插入/删除要同时维护两侧四个指针，顺序上先连新节点、再断旧关系。LRU 题里见得最多。

错法对照

错法	问题	正解
直接 curr.next = prev 不存后继	后半链表丢失、无法继续	先用 next 保存
while 条件只判 fast != null	fast.next 为 null 时再走两步崩	同时判 fast.next != null
合并不用 dummy，先单独比头	分支多、容易漏改头	dummy 占位，返回 dummy.next
接入节点后 tail 不前进	结果只剩最后一个节点	每次循环末尾 tail = tail.next
移动指针写成 head = head.next 后再用旧头	旧节点引用已丢	先完成接线，再推进指针

卡点急救

1. 空指针异常连环爆：逐个数点号——每个 .next / .val 前的对象有没有可能为 null，链表题的 NPE 全部源于此处。
2. 链表绕成环或断成两截：停止写代码，画 3～4 个节点，把每条指针的「旧状态 → 新状态」画出来，按图操作。
3. 边界（空链、单节点）出错：先拿空链和单节点走一遍你的代码——反转单节点应返回自身，这是最便宜的验证。

面试常问

• 如何找到链表环的入口？无环时返回什么？ Floyd 两阶段：快慢指针相遇点出发 + 头节点出发，两指针等速移动，相遇即入口；第一阶段 fast 先碰到 null 说明无环，返回 null。这是 141 的标准升级问法（LeetCode 142）。

• 如何 O(n) 找到链表倒数第 k 个节点？ 快指针先走 k 步，再让慢指针与快指针同速走；快指针到 null 时，慢指针正好在倒数第 k 个。一次遍历，是双指针间距法的典型应用。

• 用链表实现一个 LRU 缓存，结构怎么设计？ 哈希表 + 双向链表：map 提供 key→节点的 O(1) 定位；双向链表按访问时间排序，最新在头、最旧在尾；get/put 时把节点摘除并移到头部，超容量时删尾节点并从 map 移除。Java 的 LinkedHashMap 自带 removeEldestEntry 钩子，单机版可直接用。

自测三问

1. 反转链表的四步动作是什么？循环不变量如何描述？
2. 判环为什么用 2 倍速？换 3 倍速行不行？
3. dummy 节点解决了什么问题？合并结束为什么能整条拼接剩余链？

小结一句话

链表考的是指针纪律：断链前先存、x.next 前先判空、头会变就挂 dummy；反转靠三指针，判环靠快慢针，合并靠尾接。

延伸

• 巩固练习：LeetCode 142 环形链表 II、LeetCode 234 回文链表、LeetCode 23 合并 K 个升序链表
• 在本站在线判题平台提交，重点试空链表、单节点、链表尾自环等用例
• 下一课预告：二叉树——递归思维的主战场，层序遍历、最大深度、最近公共祖先