理解每一次指向的变化
链表技巧与 Hot 100 题解 把零散的指针操作连成清楚的思路。先掌握引用、dummy、tail 和快慢指针，再逐题练习。每道题都有题意、Java 解答、例子推演、注意点和复杂度。
14 道官方题单题目 Java 1.8 黑色代码，无彩色高亮 单文件，可离线阅读
先理解引用，再记住模板
链表技巧
每次写指针操作，都先回答：我在移动变量，还是改变节点之间的连接？先保存谁，改完后谁还握着剩余链表？
本手册统一偏好：slow = head、fast = head；找中点使用 fast != null && fast.next != null。需要从中间断开时，用 prev 保存前驱。第 19 题是固定间距指针，仍需使用它自己的停止条件。
01 / 变量换指向，节点换连接，是两回事
ListNode saved = cur; // 两个变量暂时指向同一对象
cur = cur.next; // 只移动 cur，saved 不会跟着移动
saved.next = null; // 修改 saved 所指节点的 next 字段
HashSet.add(cur)、map.put(cur, copy) 保存的是当时的引用。之后给 cur 赋另一个引用，不会替换集合中已经保存的引用；但如果修改同一个节点的字段，通过其他引用也能看到变化。Java 传参始终是值传递，对象参数传递的是引用值的副本。
02 / dummy 是起点，tail 是“穿针引线”的针
dummy → 1 → 2 → null
↑
tail
tail.next = newNode; // 先把线接上
tail = tail.next; // 再把针移过去
return dummy.next; // 返回真实头节点
dummy 固定不动。prev= dummy 时，prev.next 的修改就是在改 dummy.next。删除头节点、交换前两个节点后，head 可能不再是真实头节点，应返回 dummy.next。
03 / while 条件取决于希望停在哪里
条件 用途与停止位置
cur != null处理所有节点，包括尾节点；结束时 cur=null。 cur.next != null走到尾节点就停；必须保证 cur 本身存在。 fast != null && fast.next != null安全地执行 fast=fast.next.next；结果允许为 null。 first != null && second != null合并时两边都还有节点才比较，剩余部分整体接上。 l1 != null || l2 != null || carry != 0相加时任意一边或进位未处理完，都要继续。 ap != bp相交链表以引用相同为终点；允许同时为 null。
04 / 快慢指针统一初始化，但后续处理要配套
slow=head，fast=head，prev=null
每轮：prev=slow；slow 走 1 步；fast 走 2 步。
偶数：A → B → C → D 奇数：A → B → C → D → E
↑ ↑ ↑ ↑
prev slow prev slow
用标准条件结束后，偶数时 slow 在第二个中间节点，奇数时 slow 在正中间。第 148 题从 prev.next 断开，右半段以 slow 为头；不能跳过中间节点。第 234 题为了对齐两半，奇数时需要跳过中间节点。
固定间距双指针：先想结束时的位置，再算领先步数
第 19 题中，fast 要停在尾节点，slow 要停在待删节点的前一个节点。这两个位置之间相隔 n 步，所以从同一个 dummy 出发，让 fast 先走 n 步，再一起走。这里的 fast 只是提前出发，后面速度和 slow 相同，与找中点时“一步、两步”的模板不同。
dummy 位置 = 0，真实节点位置 = 1…L
倒数第 n 个节点的位置 = L − n + 1
它前一个节点的位置 = L − n
fast 最终位置 = L
需要保持的间距 = L − (L − n) = n
dummy.next=head 是把额外节点接到原链表前面；dummy=head 只是换一个变量名保存原头节点，不能代替前驱。查看第 19 题的逐轮位置、删除头节点示例和完整推导 →
05 / 保存后继，再反转；保存右头，再断链
反转：
ListNode next = cur.next;
cur.next = prev;
prev = cur;
cur = next;
拆分（slow 已保存右半段的头）：
prev.next = null;
sortList(head);
sortList(slow);
断链不是删除整个右半段，也不会把 slow 变成 null。只要 slow 仍引用它，右半段仍可访问。不进行断链，sortList(head) 会反复收到同一条链表。
06 / 归并的两种“拆分”
第 148 题拆一条无序链表，直到每段只有一个节点；第 23 题拆“链表数组的范围”，直到只剩一条本来有序的链表。merge 只负责合并两条已排序链表，它自己不是完整排序。
07 / 先移动，再判断相遇；值相等不代表节点相同
第 141、142 题的快慢指针初始相等，所以必须先走再比较。第 160 题查相交，使用 ap==bp；第 234 题查回文，使用节点的 val 比较。第 142 题第一次相遇点一般不是入口，还需要第二阶段。
08 / 深拷贝与原地修改要区分
第 138 题必须创建新节点，random 只能指向副本。第 21、23、24、25、148 题可以复用原节点，修改连接；如果后续仍需要原结构，要先明确是否必须恢复。第 234 题的反转版本在本手册中会恢复输入。
09 / 复杂度不要只数有几个循环
连续三次遍历是 O(n)，不是 O(n³)。K 组各反转自己的节点，总计仍是 O(n)。递归归并有 O(log n) 层、每层处理 O(n) 个节点，所以是 O(n log n)。递归会占调用栈，不能把递归归并说成 O(1) 额外空间。
10 / 提交前用这些小例子检查
空链表、单节点、两个节点；奇数长度与偶数长度。 删除头节点、删除尾节点；相等值来自不同对象。 相交发生在头部、不相交；自环、入口在头部、完全无环。 反转分组 k=1、恰好一组、末尾不足 k 个。 相加长度不同、连续进位、最后仍有进位。 random 指向自己、前面、后面或 null；副本不得指回原对象。 节点定义与提交方式 每道题的代码独立提交，不要把多个 Solution 放进同一个文件。力扣已提供节点类型；自己在 main 中运行时，可以添加下面的定义。第 146 题直接提交 LRUCache。
本地练习用 · 节点定义 复制代码
class ListNode {
int val;
ListNode next;
ListNode(int val) { this.val = val; }
}
// 第 138 题使用 Node，其余普通链表题使用 ListNode。
class Node {
int val;
Node next;
Node random;
Node(int val) { this.val = val; }
}先练会这三组，再组合使用
基础接线：206 → 21 → 2 → 24
指针定位：141 → 142 → 160 → 19 → 234
组合应用：148 → 23 → 25 → 138 → 146
LINKED LIST / 01
160 · 相交链表 题目要做什么 给定两条无环单链表的头节点，返回它们相交的第一个节点；没有交点则返回 null。相交要求是同一个节点对象，数值相等不算相交。
A：A1 → A2 ─────┐
C1 → C2 → null
B：B1 → B2 → B3 ┘
返回共享的节点 C1，而不是新建一个同值节点。 解题步骤 ap 先走 A，再走 B；bp 先走 B，再走 A。 走到 null 后，下一轮才切换到另一条链表的头节点。 当 ap == bp 时结束：可能在交点相遇，也可能同时为 null。 Java 1.8 解答 Java 1.8 · 可复制 复制代码
class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode ap = headA;
ListNode bp = headB;
while (ap != bp) {
ap = ap == null ? headB : ap.next;
bp = bp == null ? headA : bp.next;
}
return ap;
}
}用例推演 若 A 独有 a 个节点、B 独有 b 个节点、公共部分有 c 个节点，换路后到交点，两者分别经过 a+c+b 和 b+c+a 个节点，并各经历一次从 null 换路，长度差被抵消。等长链表可能第一趟就相遇。
注意点与技巧 判断 ap 本身是否为 null，不是判断 ap.next。跳过 null 状态会让不相交的非空链表无法结束。 ap == bp 比较节点身份；ap.val == bp.val 只比较数字。 移动 ap、bp 只是重新赋值局部引用，不会修改原链表的 next。 复杂度： 时间 O(m+n)，额外空间 O(1)。原链表： 不修改原链表。
LINKED LIST / 02
206 · 反转链表 题目要做什么 反转单链表的连接方向，返回新的头节点。空链表返回 null。
输入：1 → 2 → 3 → null
输出：3 → 2 → 1 → null 解题步骤 prev 保存已经反转好的部分，cur 指向当前待处理节点。 先用 next 保存原后继，再执行 cur.next = prev。 prev、cur 同时推进；cur 为 null 时，prev 是新头节点。 Java 1.8 解答 Java 1.8 · 可复制 复制代码
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;
cur = next;
}
return prev;
}
}用例推演 初始 prev=null，cur=1。处理 1 后：prev 指向 1→null，cur=2。处理 2 后：prev 指向 2→1→null，cur=3。处理 3 后：prev 指向 3→2→1→null，cur=null。返回 prev。
追加推演：用你的 slow、fast、temp 写法反转 [1,2,3,4,5]
这份代码与上面的 prev、cur、next 写法是同一个算法，只是变量名称不同。这里的 slow、fast 不是“一次走一步、一次走两步”的快慢指针，而是在维护已经反转和尚未处理的两部分。
slow：指向已经反转好的部分的头节点，对应上面的 prev。 fast：指向当前待处理的节点，对应上面的 cur。 temp：保存当前节点原来的下一个节点，对应上面的 next。 Java 1.8 · slow / fast / temp 版本 复制代码
class Solution {
public ListNode reverseList(ListNode head) {
ListNode slow = null;
ListNode fast = head;
while (fast != null) {
ListNode temp = fast.next;
fast.next = slow;
slow = fast;
fast = temp;
}
return slow;
}
}初始化：还没有反转任何节点
head → 1 → 2 → 3 → 4 → 5 → null
slow = null
fast = head，也就是节点 1
已反转部分：空
待处理部分：1 → 2 → 3 → 4 → 5 → null
第 1 轮：处理节点 1
第一句先保存后继，第二句才修改连接。后面的链表不会丢失，因为 temp 仍然保存着节点 2 的引用。
① ListNode temp = fast.next;
temp 指向节点 2，先保存剩余链表的入口。
② fast.next = slow;
slow 现在为 null，所以把节点 1 的 next 改成 null。
此时：1 → null
temp → 2 → 3 → 4 → 5 → null
③ slow = fast;
slow 指向刚处理好的节点 1。
④ fast = temp;
fast 指向节点 2，准备下一轮。
第 1 轮结束：
已反转：slow → 1 → null
待处理：fast → 2 → 3 → 4 → 5 → null
第 2 轮：处理节点 2
ListNode temp = fast.next; // temp 指向节点 3
fast.next = slow; // 让节点 2 指向节点 1
slow = fast; // slow 移到节点 2
fast = temp; // fast 移到节点 3
第 2 轮结束：
已反转：slow → 2 → 1 → null
待处理：fast → 3 → 4 → 5 → null
第 3 轮：处理节点 3
ListNode temp = fast.next; // temp 指向节点 4
fast.next = slow; // 让节点 3 指向节点 2
slow = fast; // slow 移到节点 3
fast = temp; // fast 移到节点 4
第 3 轮结束：
已反转：slow → 3 → 2 → 1 → null
待处理：fast → 4 → 5 → null
第 4 轮：处理节点 4
ListNode temp = fast.next; // temp 指向节点 5
fast.next = slow; // 让节点 4 指向节点 3
slow = fast; // slow 移到节点 4
fast = temp; // fast 移到节点 5
第 4 轮结束：
已反转：slow → 4 → 3 → 2 → 1 → null
待处理：fast → 5 → null
第 5 轮：处理节点 5
ListNode temp = fast.next; // temp = null，已经没有后继
fast.next = slow; // 让节点 5 指向节点 4
slow = fast; // slow 移到节点 5
fast = temp; // fast = null
第 5 轮结束：
已反转：slow → 5 → 4 → 3 → 2 → 1 → null
待处理：空，fast = null
此时 fast != null 不成立，退出循环，返回 slow，也就是新的头节点 5。
把每一轮的结果放在一起看
初始： slow → null
第 1 轮：slow → 1 → null
第 2 轮：slow → 2 → 1 → null
第 3 轮：slow → 3 → 2 → 1 → null
第 4 轮：slow → 4 → 3 → 2 → 1 → null
第 5 轮：slow → 5 → 4 → 3 → 2 → 1 → null
每一轮都从待处理部分取出一个节点，接到已反转部分的最前面。先保存后继，再改变 next，最后移动两个变量。
为什么返回 slow，而不是 head？
整个方法里没有给 head 重新赋值，所以 head 一直指向原来的节点 1。反转改变的是节点之间的连接，不会让 head 自动指向新的头节点。
结束时：
slow 指向节点 5：5 → 4 → 3 → 2 → 1 → null
head 指向节点 1：1 → null
return slow; // 返回完整的反转链表
return head; // 只能从原头节点 1 开始走，漏掉前面的 5、4、3、2
注意点与技巧 不能先改 cur.next 再读取旧后继；那样可能丢失剩余链表。 prev = cur 是移动变量的指向；cur.next = prev 是改变节点连接。 最后返回 prev，而不是原来的 head；原 head 已经变成尾节点。 复杂度： 时间 O(n)，额外空间 O(1)。原链表： 原地改变 next 连接。
LINKED LIST / 03
234 · 回文链表 题目要做什么 判断链表从前往后与从后往前的节点值序列是否相同。进阶要求时间 O(n)、额外空间 O(1)。
1 → 2 → 2 → 1：true
1 → 2 → 3 → 2 → 1：true
1 → 2：false 解题步骤 使用你熟悉的 slow=head、fast=head，以及 fast!=null && fast.next!=null。 每轮把 slow 入栈，再让 slow 走一步、fast 走两步。 若 fast 不为 null，长度为奇数，让 slow 再走一步，跳过中间节点。 栈顶依次对应前半段的倒序，与后半段顺序比较。 Java 1.8 解答 Java 1.8 · 可复制 复制代码
import java.util.ArrayDeque;
import java.util.Deque;
class Solution {
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) return true;
Deque<ListNode> stack = new ArrayDeque<>();
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
stack.push(slow);
slow = slow.next;
fast = fast.next.next;
}
if (fast != null) slow = slow.next;
while (!stack.isEmpty()) {
if (stack.pop().val != slow.val) return false;
slow = slow.next;
}
return true;
}
}用例推演 1→2→3→2→1：第一轮栈为 [1]，slow 指向第 2 个节点；第二轮栈为 [1,2]（右侧是栈顶），slow 指向 3，fast 指向最后的 1。跳过中间的 3，依次比较 2 和 2、1 和 1。
注意点与技巧 HashSet 不能代替栈：这里需要保留出现次序和重复值。 比较循环不要用 slow.next != null，否则最后一个节点会漏比较。 奇数判断是为了让比较起点对齐，不是所有快慢指针题都必须判断奇偶。 下面的反转版本才满足 O(1) 额外空间，并且在返回前恢复原链表。 复杂度： 栈方案：时间 O(n)，额外空间 O(n)。反转方案：时间 O(n)，额外空间 O(1)。原链表： 主解不修改链表；反转版本暂时修改，最后恢复。
进阶：反转后半段，O(1) 额外空间（统一快慢指针模板） 比较只走到 p2 为空。保留 secondHead 用于恢复，不能在发现不相等时直接 return false。反转并恢复的是同一批节点，不创建新节点。
Java 1.8 · 可复制 复制代码
class Solution {
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) return true;
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// 偶数：slow 已在后半段；奇数：跳过正中间。
if (fast != null) slow = slow.next;
ListNode secondHead = reverse(slow);
ListNode p1 = head;
ListNode p2 = secondHead;
boolean result = true;
while (p2 != null) {
if (p1.val != p2.val) {
result = false;
break;
}
p1 = p1.next;
p2 = p2.next;
}
reverse(secondHead); // 原先通向后半段头节点的连接一直保留着
return result;
}
private ListNode reverse(ListNode head) {
ListNode prev = null;
ListNode cur = head;
while (cur != null) {
ListNode next = cur.next;
cur.next = prev;
prev = cur;
cur = next;
}
return prev;
}
}LINKED LIST / 04
141 · 环形链表 题目要做什么 判断链表是否有环，返回 true 或 false。pos 只是题目描述尾节点连到哪里，不是方法参数。
A → B → C → D
↑ │
└───────┘
返回 true。 解题步骤 slow、fast 都从 head 出发。 每轮先移动：slow 走一步，fast 走两步。 移动后相遇说明有环；fast 或 fast.next 为 null 则无环。 Java 1.8 解答 Java 1.8 · 可复制 复制代码
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;
}
}用例推演 两指针都进入长度为 L 的环后，每轮 fast 比 slow 多走一步，两者的相对位置每轮变化 1（模 L），因此最多再经过 L 轮就会相遇。无环时 fast 会到达链表末尾。
注意点与技巧 初始 slow == fast 不代表有环，必须先移动再比较。 相等比较的是节点引用，不是 val；相同数字可能来自不同节点。 fast.next.next 可以是 null，赋值允许得到 null；被访问的 fast 和 fast.next 必须存在。 复杂度： 时间 O(n)，额外空间 O(1)。原链表： 不修改链表。
LINKED LIST / 05
142 · 环形链表 II 题目要做什么 若链表有环，返回开始入环的第一个节点；无环返回 null。不能修改链表。
A → B → C → D
↑ │
└───────┘
返回节点 B。 解题步骤 第一阶段按 141 的方式找到快慢指针相遇的位置。 一个指针从 head 出发，另一个从相遇位置出发。 两个指针每次都走一步，再次相遇的位置就是环入口。 Java 1.8 解答 Java 1.8 · 可复制 复制代码
class Solution {
public ListNode detectCycle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
ListNode entry = head;
while (entry != slow) {
entry = entry.next;
slow = slow.next;
}
return entry;
}
}
return null;
}
}用例推演 设头到入口距离为 a，入口到相遇点沿 next 的距离为 b，环长为 L。相遇时慢指针走了 s=a+b+tL 步，快指针走了 2s 步，差值 s=qL。于是 a+b 是 L 的整数倍。相遇点再走 a 步，恰好回到入口；从 head 走 a 步也到入口。
注意点与技巧 第一次相遇点通常不是入口，需要第二阶段。 这段证明对应两个指针都从 head 出发、速度为 1 和 2 的模板，不要只改初始化。 HashSet 也能做：第一次添加失败的节点就是入口，但额外空间为 O(n)。 复杂度： 时间 O(n)，额外空间 O(1)。原链表： 不修改链表。
LINKED LIST / 06
21 · 合并两个有序链表 题目要做什么 将两条升序链表合并为一条升序链表，返回头节点。可以复用输入节点。
输入：1 → 2 → 4；1 → 3 → 4
输出：1 → 1 → 2 → 3 → 4 → 4 解题步骤 dummy 固定保存结果的起点，tail 指向已经选好部分的最后一个节点。 比较两边当前值，把较小的节点接到 tail.next，再推进对应输入指针。 tail 前进一步。一边为空时，直接接上另一边的剩余链表。 Java 1.8 解答 Java 1.8 · 可复制 复制代码
class Solution {
public ListNode mergeTwoLists(ListNode first, ListNode second) {
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
while (first != null && second != null) {
if (first.val <= second.val) {
tail.next = first;
first = first.next;
} else {
tail.next = second;
second = second.next;
}
tail = tail.next;
}
tail.next = first != null ? first : second;
return dummy.next;
}
}用例推演 合并 [2,4] 和 [1,3]：先接 1，tail 移到 1；再接 2，tail 移到 2；再接 3，tail 移到 3；右边为空，把剩余的 4 接到 tail.next。最后一次整体接上剩余链表后，不必再移动 tail。
注意点与技巧 先执行 tail.next = first/second，再执行 tail = tail.next；不能直接交换这两步。 tail.next 修改节点对象，tail = tail.next 只移动引用。 dummy 一直指向虚拟节点，返回 dummy.next，不是 dummy。 这是合并步骤，不是完整排序；两条输入链表必须已经有序。 复杂度： 时间 O(m+n)，额外空间 O(1)。原链表： 复用原节点并改变 next 连接。
LINKED LIST / 07
2 · 两数相加 题目要做什么 两个非空链表按逆序保存非负整数，每个节点是一位数字。返回两数之和的逆序链表，不把整个链表转成 int 或 long。
2 → 4 → 3 表示 342
5 → 6 → 4 表示 465
结果：7 → 0 → 8，表示 807 解题步骤 个位在头部，从左到右同时遍历；某条链表结束时，该位按 0 处理。 sum = x + y + carry；当前位为 sum % 10，新进位为 sum / 10。 只要任一链表还未结束，或者仍有进位，就继续创建结果节点。 Java 1.8 解答 Java 1.8 · 可复制 复制代码
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
int carry = 0;
while (l1 != null || l2 != null || carry != 0) {
int x = l1 == null ? 0 : l1.val;
int y = l2 == null ? 0 : l2.val;
int sum = x + y + carry;
tail.next = new ListNode(sum % 10);
tail = tail.next;
carry = sum / 10;
if (l1 != null) l1 = l1.next;
if (l2 != null) l2 = l2.next;
}
return dummy.next;
}
}用例推演 342+465：第一轮 2+5+0=7，写 7，进位 0；第二轮 4+6+0=10，写 0，进位 1；第三轮 3+4+1=8，写 8，进位 0。99+1 则需要额外一轮把最后的进位 1 写入，得到 0→0→1。
注意点与技巧 循环条件是或 ||，不能用 &&：长度不同或还有进位时仍需处理。 tail.next = new ListNode(...) 先连接；tail = tail.next 再移动。初始时倒过来会让 tail 变成 null。 输入可能远超整数范围，应逐位计算。单次 sum 最大为 9+9+1=19。 复杂度： 时间 O(max(m,n))；不计返回链表，额外空间 O(1)。原链表： 创建新结果节点，不修改输入链表。
LINKED LIST / 08
19 · 删除链表的倒数第 N 个结点 题目要做什么 删除单链表倒数第 n 个节点并返回头节点。题目保证 1 ≤ n ≤ 链表长度，要求一趟扫描。
1 → 2 → 3 → 4 → 5，n=2
结果：1 → 2 → 3 → 5 解题步骤 使用 dummy 统一处理删除头节点的情况。两个指针都从 dummy 出发。 fast 先走 n 步，再让 slow、fast 同速前进。 当 fast 停在尾节点，slow 指向待删除节点的前一个节点，跳过 slow.next。 Java 1.8 解答 Java 1.8 · 可复制 复制代码
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode slow = dummy;
ListNode fast = dummy;
for (int i = 0; i < n; i++) fast = fast.next;
while (fast.next != null) {
slow = slow.next;
fast = fast.next;
}
slow.next = slow.next.next;
return dummy.next;
}
}用例推演 n=2：fast 先从 dummy 走到节点 2；然后两者一起走，最终 fast=5，slow=3。修改 3.next，让它越过 4 指向 5。若 n 等于链表长度，slow 停在 dummy，修改 dummy.next 即可删除原头节点。
从目标位置反推间距： fast 停在尾节点时，slow 必须停在待删除节点的前一个节点。因此先让 fast 领先 n 步，再让两者同速移动。
为什么先走 n 步，不是 n − 1 步？
从倒数第 n 个节点到尾节点，需要 n−1 步。但删除时要修改的是它前一个节点的 next，所以 slow 还要往前多留一个位置：间距 = 1 + (n−1) = n。
链表：1 → 2 → 3 → 4 → 5，n = 2
目标：删除节点 4，让 slow 停在节点 3。
slow 在节点 3，fast 在节点 5：
节点 3 ──第 1 步──→ 节点 4 ──第 2 步──→ 节点 5
3 到 5 相隔 2 条 next 连接，所以 fast 要领先 2 步。
这里数的是“移动次数”，不是两端一共包含几个节点。
每一轮的位置：1 → 2 → 3 → 4 → 5，n = 2
阶段 slow 在哪里 fast 在哪里 说明
初始化 dummy dummy 同一起点，距离为 0 fast 先走第 1 步 dummy 节点 1 dummy → 1 算一步 fast 先走第 2 步 dummy 节点 2 间距建立为 n = 2 一起走，第 1 轮 节点 1 节点 3 两者各走一步，间距仍为 2 一起走，第 2 轮 节点 2 节点 4 间距仍为 2 一起走，第 3 轮 节点 3 节点 5 fast.next 为 null，停止
最后执行 slow.next = slow.next.next，相当于让节点 3 的 next 指向节点 5，跳过节点 4。结果为 1 → 2 → 3 → 5。
为什么从 dummy 出发？为了统一删除头节点
比如 1 → 2 → 3，n=3，要删除头节点 1。fast 从 dummy 出发走三步：dummy → 1 → 2 → 3，恰好到尾节点；slow 仍然留在 dummy。后面的 while 一次也不执行，直接修改 dummy.next 就能删除节点 1。
删除前：dummy → 1 → 2 → 3 → null
slow fast
执行：slow.next = slow.next.next
删除后：dummy → 2 → 3 → null
返回：dummy.next，也就是节点 2。
dummy.next = head，和 dummy = head 有什么不同？
ListNode dummy = new ListNode(0);
dummy.next = head;
结构：dummy → 1 → 2 → 3
↑
head
有一个额外节点，可以作为原头节点的前驱。
ListNode dummy = head;
结构：1 → 2 → 3
↑
head、dummy
只是两个变量指向同一个节点，没有多出前驱。
如果 dummy 直接指向节点 1，修改 dummy.next 会影响节点 1 后面的连接，不能用它来跳过节点 1。虚拟头节点的价值，是让删除头节点也能使用和删除其他节点相同的一句代码。
用下标再验证一次
设链表长度为 L，把 dummy 的位置记为 0，真实节点的位置记为 1 到 L。倒数第 n 个节点的位置是 L−n+1，它的前一个节点是 L−n。fast 结束在 L，始终领先 n 步，所以 slow 的位置就是 L−n，恰好是需要的位置。
这一组条件要配套： 两个指针从 dummy 出发 → fast 先走 n 步 → 两者每次各走一步 → 用 fast.next != null 控制循环，让 fast 停在尾节点 → slow 正好在待删除节点之前。不要只把停止条件改成 fast != null，否则 slow 会多走一步。
注意点与技巧 这是固定间距双指针，两个指针不是每轮分别走 1、2 步。 此处停止在 fast.next == null，是为了让 slow 停在待删节点前面。 n 的合法性由题目保证。返回 dummy.next，删除头节点时它会改变。 复杂度： 时间 O(L)，额外空间 O(1)，L 为链表长度。原链表： 改变原链表的连接。
LINKED LIST / 09
24 · 两两交换链表中的节点 题目要做什么 交换每一对相邻节点，不能只交换节点中的值。节点个数为奇数时，末尾单独的节点保留。
1 → 2 → 3 → 4 → 5
结果：2 → 1 → 4 → 3 → 5 解题步骤 prev 始终指向当前待交换的一对节点之前。 保存 first、second，先让 first 接住后续，再让 second 指回 first。 prev.next 接到 second；交换后 first 是本组尾节点，让 prev=first。 Java 1.8 解答 Java 1.8 · 可复制 复制代码
class Solution {
public ListNode swapPairs(ListNode head) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode prev = dummy;
while (prev.next != null && prev.next.next != null) {
ListNode first = prev.next;
ListNode second = first.next;
first.next = second.next;
second.next = first;
prev.next = second;
prev = first;
}
return dummy.next;
}
}用例推演 原来 prev→1→2→3：先 1.next=3，再 2.next=1，最后 prev.next=2，得到 prev→2→1→3。然后 prev 移到 1，准备处理 3 和 4。
注意点与技巧 首轮 prev 和 dummy 指向同一个对象，因此 prev.next = second 会改变 dummy.next。 head 仍然指向原节点 1，而新的头是节点 2，所以不能返回 head。 条件检查两个待交换节点存在。每轮结束 prev 应移动到 first，不是 second。 复杂度： 时间 O(n)，额外空间 O(1)。原链表： 只改变连接，不修改节点值。
LINKED LIST / 10
25 · K 个一组翻转链表 题目要做什么 每 k 个节点为一组反转；末尾不足 k 个的部分保持原顺序。不能仅交换值，题目保证 k≥1。
1 → 2 → 3 → 4 → 5，k=2
结果：2 → 1 → 4 → 3 → 5 解题步骤 groupPrev 指向本组之前，向后检查 k 个节点是否齐全。 记录 kth、groupNext 和 groupStart；不足 k 个直接结束。 让 prev 初始指向 groupNext，反转到 cur==groupNext 为止。 前组接到 kth，新组尾是原来的 groupStart，用它作为下一轮 groupPrev。 Java 1.8 解答 Java 1.8 · 可复制 复制代码
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode groupPrev = dummy;
while (true) {
ListNode kth = groupPrev;
for (int i = 0; i < k && kth != null; i++) {
kth = kth.next;
}
if (kth == null) break;
ListNode groupNext = kth.next;
ListNode groupStart = groupPrev.next;
ListNode prev = groupNext;
ListNode cur = groupStart;
while (cur != groupNext) {
ListNode next = cur.next;
cur.next = prev;
prev = cur;
cur = next;
}
groupPrev.next = kth;
groupPrev = groupStart;
}
return dummy.next;
}
}用例推演 k=2，首组 [1,2]，groupNext=3。prev 初始为 3；反转时先让 1.next=3，再让 2.next=1。把 dummy.next 接到 2，得到 2→1→3→4→5；groupPrev 移到 1。末尾只剩 5 时检查不够两个，保持不变。
注意点与技巧 必须先确认有 k 个节点，不能反转了一部分才发现不够。 提前保存 groupNext；不能把循环条件写成 cur != kth.next，因为 kth.next 会在反转时改变。 每组的原头变成新尾，groupPrev 应移动到 groupStart。 复杂度： 时间 O(n)，额外空间 O(1)。原链表： 原地改变 next 连接。
LINKED LIST / 11
138 · 随机链表的复制 题目要做什么 每个节点包含 val、next、random。构造深拷贝：所有新节点的 next、random 都只能指向新节点或 null，不能指向原链表节点。
原链：A(7) → B(13) → C(11)，B.random=A
新链：A′(7) → B′(13) → C′(11)，B′.random=A′
A 与 A′ 是不同对象。 解题步骤 第一遍为每个原节点创建副本，用 HashMap 保存原节点到副本的映射。 第二遍连接副本：copy.next=map.get(cur.next)，random 同理。 返回原头节点对应的副本；空链表自然返回 null。 Java 1.8 解答 Java 1.8 · 可复制 复制代码
import java.util.HashMap;
import java.util.Map;
class Solution {
public Node copyRandomList(Node head) {
Map<Node, Node> map = new HashMap<>();
Node cur = head;
while (cur != null) {
map.put(cur, new Node(cur.val));
cur = cur.next;
}
cur = head;
while (cur != null) {
Node copy = map.get(cur);
copy.next = map.get(cur.next);
copy.random = map.get(cur.random);
cur = cur.next;
}
return map.get(head);
}
}用例推演 第一遍得到 A→A′、B→B′、C→C′ 的映射。若 A.random=C，第二遍通过 map.get(C) 找到 C′，再令 A′.random=C′。因此即使 random 指向后面的节点，也不会因为副本尚未创建而出错。
注意点与技巧 键是原节点对象，不是 val；多个节点的值可以相同。题目 Node 没有重写 equals/hashCode。 copy.random = cur.random 是错误的浅连接，它会指回原节点。 map.get(null) 在这里返回 null，因为从未存入 null 键。 交错复制的版本见下方，它不需要 HashMap，但会暂时修改原链表。 复杂度： 哈希方案：平均时间 O(n)，额外空间 O(n)。交错复制：时间 O(n)，额外空间 O(1)。均不计新链表。原链表： 主解不修改输入；交错复制会暂时修改，最后恢复。
进阶：交错复制，再拆分（不使用 HashMap） A→A′→B→B′→C→C′：每个原节点的 next 就是副本。若 A.random=C，则 A′.random=C.next=C′。设置完 random 再拆分；先保存 newHead，拆分时同时恢复原链表。
Java 1.8 · 可复制 复制代码
class Solution {
public Node copyRandomList(Node head) {
if (head == null) return null;
Node cur = head;
while (cur != null) {
Node copy = new Node(cur.val);
copy.next = cur.next;
cur.next = copy;
cur = copy.next;
}
cur = head;
while (cur != null) {
Node copy = cur.next;
copy.random = cur.random == null ? null : cur.random.next;
cur = copy.next;
}
Node newHead = head.next;
cur = head;
while (cur != null) {
Node copy = cur.next;
Node nextOriginal = copy.next;
cur.next = nextOriginal;
copy.next = nextOriginal == null ? null : nextOriginal.next;
cur = nextOriginal;
}
return newHead;
}
}LINKED LIST / 12
148 · 排序链表 题目要做什么 将单链表按升序排序并返回新的头节点。目标时间复杂度 O(n log n)；进阶要求常量额外空间。主解先用容易理解的递归归并。
输入：4 → 2 → 1 → 3
输出：1 → 2 → 3 → 4 解题步骤 slow、fast 都从 head 出发，prev 保存 slow 的前一个节点。 循环结束时 slow 是右半段的头，prev 是左半段尾。执行 prev.next=null 断开。 分别递归排序 head 和 slow 开始的链表，再合并两个有序结果。 Java 1.8 解答 Java 1.8 · 可复制 复制代码
class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode slow = head;
ListNode fast = head;
ListNode prev = null;
while (fast != null && fast.next != null) {
prev = slow;
slow = slow.next;
fast = fast.next.next;
}
prev.next = null;
ListNode left = sortList(head);
ListNode right = sortList(slow);
return merge(left, right);
}
private ListNode merge(ListNode first, ListNode second) {
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
while (first != null && second != null) {
if (first.val <= second.val) {
tail.next = first;
first = first.next;
} else {
tail.next = second;
second = second.next;
}
tail = tail.next;
}
tail.next = first != null ? first : second;
return dummy.next;
}
}用例推演 4→2→1→3：循环结束 prev 指向 2，slow 指向 1。断开后为 [4,2] 和 [1,3]。左边先拆成 [4]、[2]，合并成 [2,4]；右边合并成 [1,3]；最后合并为 [1,2,3,4]。递归会等子调用完成，才继续执行 merge。
注意点与技巧 不能省略 prev.next=null，否则 sortList(head) 仍收到原来的整条链表，递归无法缩小。 prev.next=null 不会让 slow 变成 null；slow 已保存右半段的引用。 不用跳过奇数链表的中间节点，排序必须保留全部节点。 主解用了递归栈，因此不是 O(1) 额外空间。严格进阶解法见下方。 复杂度： 主解时间 O(n log n)，额外空间 O(log n)。迭代进阶时间 O(n log n)，额外空间 O(1)。原链表： 复用原节点并改变连接。
进阶：自底向上归并，严格 O(1) 额外空间 每轮合并的块长按 1、2、4、8…增长。cut 真正断开每个块；合并后 tail 走到块尾，为下一组合并作准备。没有递归，不需要存放与 n 成比例的数组。
Java 1.8 · 可复制 复制代码
class Solution {
public ListNode sortList(ListNode head) {
int n = 0;
for (ListNode p = head; p != null; p = p.next) n++;
ListNode dummy = new ListNode(0);
dummy.next = head;
for (int size = 1; size < n; ) {
ListNode tail = dummy;
ListNode cur = dummy.next;
while (cur != null) {
ListNode first = cur;
ListNode second = cut(first, size);
cur = cut(second, size);
while (first != null && second != null) {
if (first.val <= second.val) {
tail.next = first;
first = first.next;
} else {
tail.next = second;
second = second.next;
}
tail = tail.next;
}
tail.next = first != null ? first : second;
while (tail.next != null) tail = tail.next;
}
if (size > n / 2) break; // 避免翻倍溢出
size *= 2;
}
return dummy.next;
}
// 从 head 起截取最多 size 个节点，返回余下部分的头。
private ListNode cut(ListNode head, int size) {
if (head == null) return null;
for (int i = 1; i < size && head.next != null; i++) {
head = head.next;
}
ListNode rest = head.next;
head.next = null;
return rest;
}
}LINKED LIST / 13
23 · 合并 K 个升序链表 题目要做什么 给定链表数组 lists，每个元素是一条升序链表的头节点。合并所有链表并返回升序结果；数组可以为空，元素也可以为 null。
lists[0]：1 → 4 → 5
lists[1]：1 → 3 → 4
lists[2]：2 → 6
结果：1 → 1 → 2 → 3 → 4 → 4 → 5 → 6 解题步骤 划分的是链表数组的下标范围，不是某条链表的节点，因此直接计算 mid。 left==right 时只有一条链表，本来就有序，直接返回 lists[left]。 递归合并左右两组，最后调用与 21、148 相同的 merge。 Java 1.8 解答 Java 1.8 · 可复制 复制代码
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0) return null;
return mergeRange(lists, 0, lists.length - 1);
}
private ListNode mergeRange(ListNode[] lists, int left, int right) {
if (left == right) return lists[left];
int mid = left + (right - left) / 2;
ListNode first = mergeRange(lists, left, mid);
ListNode second = mergeRange(lists, mid + 1, right);
return merge(first, second);
}
private ListNode merge(ListNode first, ListNode second) {
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
while (first != null && second != null) {
if (first.val <= second.val) {
tail.next = first;
first = first.next;
} else {
tail.next = second;
second = second.next;
}
tail = tail.next;
}
tail.next = first != null ? first : second;
return dummy.next;
}
}用例推演 范围 [0,2] 的 mid=1，先合并 [0,1]，再处理 [2,2]。[0,1] 分为 [0,0] 和 [1,1]，合成 1→1→3→4→4→5；[2,2] 直接返回 2→6；最后合并两条结果。
注意点与技巧 right 是包含在范围内的最后一个下标，所以传 lists.length-1，而不是 lists.length。 只剩一条链表不等于只剩一个节点；这与 148 的递归终止条件不同。 mid 公式避免 left+right 溢出；数组可按下标访问，不需要快慢指针。 顺序合并也正确，但结果不断变长，最坏可能产生 O(NK) 的重复扫描。 复杂度： K 为链表数、N 为总节点数。K≥2 时总时间 O(K+N log K)，包含空链表的分组开销；递归栈 O(log K)。K≤1 为 O(1)。原链表： 复用节点并改变 next 连接。
对照：按顺序依次合并（更直观，最坏更慢） 时间上界 O(K+NK)，额外空间 O(1)。分治让每个节点最多在 O(log K) 层合并中参与处理；顺序合并可能在每次接入新链表时反复扫描旧结果。
Java 1.8 · 可复制 复制代码
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null) return null;
ListNode result = null;
for (ListNode head : lists) {
result = merge(result, head);
}
return result;
}
private ListNode merge(ListNode first, ListNode second) {
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
while (first != null && second != null) {
if (first.val <= second.val) {
tail.next = first;
first = first.next;
} else {
tail.next = second;
second = second.next;
}
tail = tail.next;
}
tail.next = first != null ? first : second;
return dummy.next;
}
}LINKED LIST / 14
146 · LRU 缓存 题目要做什么 实现容量固定的 LRUCache：get(key) 返回值或 -1；put(key,value) 写入或更新。超过容量时淘汰最久未使用的键。get 成功和 put 都算使用，两个操作要求平均 O(1)。题目保证 capacity≥1。
容量 2
put(1,1), put(2,2)
get(1) → 1，键 1 成为最近使用
put(3,3) → 淘汰键 2
get(2) → -1 解题步骤 HashMap 根据 key 快速定位节点；双向链表维护使用顺序。 head 后是最近使用，tail 前是最久未使用；两个哨兵统一边界操作。 访问或更新节点时，先摘下，再放到头部。容量超限时，摘掉 tail.prev，并同步删除 map 中的键。 Java 1.8 解答 Java 1.8 · 可复制 复制代码
import java.util.HashMap;
import java.util.Map;
class LRUCache {
private static class Entry {
int key;
int value;
Entry prev;
Entry next;
Entry(int key, int value) {
this.key = key;
this.value = value;
}
}
private final int capacity;
private final Map<Integer, Entry> map = new HashMap<>();
private final Entry head = new Entry(0, 0);
private final Entry tail = new Entry(0, 0);
public LRUCache(int capacity) {
this.capacity = capacity;
head.next = tail;
tail.prev = head;
}
public int get(int key) {
Entry node = map.get(key);
if (node == null) return -1;
remove(node);
addFirst(node);
return node.value;
}
public void put(int key, int value) {
Entry node = map.get(key);
if (node != null) {
node.value = value;
remove(node);
addFirst(node);
return;
}
node = new Entry(key, value);
map.put(key, node);
addFirst(node);
if (map.size() > capacity) {
Entry oldest = tail.prev;
remove(oldest);
map.remove(oldest.key);
}
}
private void remove(Entry node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
private void addFirst(Entry node) {
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
}
}用例推演 只展示键，左侧最近使用：put(1) 得 [1]；put(2) 得 [2,1]；get(1) 后为 [1,2]；put(3) 暂时为 [3,1,2]，超限删除尾部 2，剩 [3,1]。更新已有键不会增加容量占用，但会刷新使用顺序。
注意点与技巧 单链表删除任意节点需要找前驱；双向链表已保存 prev，才能常数时间摘除。 HashMap 和链表必须同步增删，淘汰时不要只改其中一个。 addFirst 的接线顺序不能随意交换，head.next 还用于找到原第一个节点。 这份实现针对单线程题目，不是线程安全的生产缓存。 复杂度： get、put 平均时间 O(1)，空间 O(capacity)。原链表： 缓存内部维护新建的双向链表节点。