算法面试突击手册 —— 链表
一、概念与特点
大白话 + 类比
链表 = 一列人手拉手
每个人只知道前面是谁（单链表）或前面+后面都知道（双向链表）。要插入一个人，只需让旁边两人重新拉手即可（O(1)）；但要找到第 100 个人，必须从第 1 个人开始数（O(n)）。
链表题目不像数组那样靠下标硬算，而是靠指针的灵活操控。核心能力就是”画图 + 把指针指来指去不出错”。
核心特征（什么时候该想到用它）
| 特征 | 说明 |
|---|---|
| 不需要随机访问 | 只关心顺序，不关心下标 |
| 频繁插入/删除 | O(1) 操作，只需改指针 |
| LRU / 缓存 | HashMap + 双向链表 |
| 翻转、合并、找环 | 链表经典题型 |
识别信号词
- “链表”、“结点” → 直接是链表题
- “O(1) 空间”、“原地” → 用指针操作而非额外数组
- “反转”、“翻转” → pre/cur/nxt 三指针
- “环”、“是否循环” → 快慢指针
- “倒数第 N 个” → 双指针间隔 N
- “合并”、“K 个一组” → dummy 节点 + 模拟
链表题必备技巧
| 技巧 | 用途 |
|---|---|
| dummy 节点 | 简化头节点操作，统一逻辑 |
| 快慢指针 | 找中点、判圈、倒数第 K |
| pre/cur/nxt 三指针 | 反转链表 |
| 画图 | 所有链表题开始写代码前先画图 |
二、应用场景
链表节点定义（假设题目给的）
public class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}三、Hot 100 精讲题目
206. Reverse Linked List 反转链表
📌 反转一个单链表。如
1→2→3→4→5→5→4→3→2→1
🔍 解题分析
核心思路：三指针 pre（前一个）、cur（当前）、nxt（下一个）。每一步让 cur 指向 pre，然后三人组集体右移。
✅ 完整 Java 实现
public ListNode reverseList(ListNode head) {
ListNode pre = null; // 前一个节点（反转后 cur 要指向的人）
ListNode cur = head; // 当前正在反转的节点
while (cur != null) {
ListNode nxt = cur.next; // 先记住下一个，免得断链后找不到了
cur.next = pre; // 反转：当前节点指向前一个
pre = cur; // 三人组右移
cur = nxt;
}
return pre; // 反转后 pre 就是新的头节点
}⏱ 复杂度分析
- 时间复杂度：O(n)
- 空间复杂度：O(1)
💡 记忆口诀
“pre cur nxt 三人组，cur 指 pre，然后全右移”
160. Intersection of Two Linked Lists 相交链表
📌 找到两个单链表相交的起始节点。不相交返回 null。
🔍 解题分析
核心思路（浪漫相遇）：双指针 pA 和 pB 分别从两个头出发。pA 走到 A 的末尾后跳到 B 的头继续走；pB 同理。两人走过的总路程相等（A 独有 + B 独有 + 公共部分），必在相交点相遇。
类比：两个人走不同的路，但最终都走了相同的总路程，一定同时到达相遇点。
✅ 完整 Java 实现
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) return null;
ListNode pA = headA, pB = headB;
// pA 和 pB 走同样的总路程，要么在交点相遇，要么同时为 null
while (pA != pB) {
pA = (pA == null) ? headB : pA.next;
pB = (pB == null) ? headA : pB.next;
}
return pA; // 可能是交点，也可能是 null
}⏱ 复杂度分析
- 时间复杂度：O(m + n)
- 空间复杂度：O(1)
💡 记忆口诀
“走完自己的路，去走对方的路，终会相遇”
234. Palindrome Linked List 回文链表
📌 判断链表是否为回文链表。要求 O(n) 时间，O(1) 空间。
🔍 解题分析
核心思路：快慢指针找中点 → 反转后半段 → 前后对比 → （可选）恢复链表。
步骤：
- 快慢指针找中点（偶数个时慢指针停在左中点）
- 反转后半段链表
- 前后双指针同时走，逐个比较
- 比较完后可恢复链表（反转回来）
✅ 完整 Java 实现
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) return true;
// 1. 快慢指针找中点
ListNode slow = head, fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// slow 现在指向左中点
// 2. 反转后半段
ListNode secondHalf = reverseList(slow.next);
// 3. 比较前后两半
ListNode p1 = head, p2 = secondHalf;
boolean isPalindrome = true;
while (p2 != null) {
if (p1.val != p2.val) {
isPalindrome = false;
break;
}
p1 = p1.next;
p2 = p2.next;
}
// 4. 恢复链表（可选，但面试建议做）
slow.next = reverseList(secondHalf);
return isPalindrome;
}
// 复用 206 题的反转函数
private ListNode reverseList(ListNode head) {
ListNode pre = null, cur = head;
while (cur != null) {
ListNode nxt = cur.next;
cur.next = pre;
pre = cur;
cur = nxt;
}
return pre;
}⏱ 复杂度分析
- 时间复杂度：O(n)
- 空间复杂度：O(1)
💡 记忆口诀
“中点切开，后半反转，同步对比”
141. Linked List Cycle 环形链表
📌 判断链表是否有环。
🔍 解题分析
快慢指针（Floyd 判圈）：快指针每次走 2 步，慢指针每次走 1 步。如果有环，快慢一定会相遇；如果没环，快指针会走到 null。
类比：就像操场跑步，跑得快的迟早会套圈跑得慢的。
✅ 完整 Java 实现
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null) return false;
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; // fast 走到 null，没环
}⏱ 复杂度分析
- 时间复杂度：O(n)
- 空间复杂度：O(1)
💡 记忆口诀
“一快一慢，相遇就有环”
142. Linked List Cycle II 环形链表 II
📌 找到环的入口节点。无环返回 null。
🔍 解题分析
核心思路（数学推导）：
- 快慢指针相遇（同 141 题）
- 相遇后，一个指针回到 head，两个指针同速前进
- 再次相遇的点就是环的入口
为什么：设 head 到入口距离 = a，入口到相遇点距离 = b，环剩余长度 = c。相遇时 slow 走了 a+b，fast 走了 a+b+n(b+c)。因为 fast 速度是 slow 两倍：2(a+b) = a+b+n(b+c) → a = (n-1)(b+c) + c。所以从 head 走的和从相遇点走的，各走 a 步后必在入口相遇。
✅ 完整 Java 实现
public ListNode detectCycle(ListNode head) {
if (head == null || head.next == null) return null;
// 1. 快慢指针找相遇点
ListNode slow = head, fast = head;
ListNode meetPoint = null;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
meetPoint = slow;
break;
}
}
if (meetPoint == null) return null; // 无环
// 2. head 和相遇点同速前进，再次相遇即入口
ListNode p1 = head, p2 = meetPoint;
while (p1 != p2) {
p1 = p1.next;
p2 = p2.next;
}
return p1;
}⏱ 复杂度分析
- 时间复杂度：O(n)
- 空间复杂度：O(1)
💡 记忆口诀
“相遇后一人回起点，两人同速走到相遇就是入口”
21. Merge Two Sorted Lists 合并两个有序链表
📌 合并两个升序链表为一个升序链表。
🔍 解题分析
核心思路：归并的链表版。dummy 节点统一逻辑，cur 尾插。每次取两个头中较小的接到 cur 后面。
✅ 完整 Java 实现
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode dummy = new ListNode(0); // 哨兵节点，简化头操作
ListNode cur = dummy;
while (list1 != null && list2 != null) {
if (list1.val <= list2.val) {
cur.next = list1;
list1 = list1.next;
} else {
cur.next = list2;
list2 = list2.next;
}
cur = cur.next;
}
// 剩下的直接接上去
cur.next = (list1 != null) ? list1 : list2;
return dummy.next;
}⏱ 复杂度分析
- 时间复杂度：O(m + n)
- 空间复杂度：O(1)
💡 记忆口诀
“dummy 坐镇，谁小接谁，剩下的直接挂”
2. Add Two Numbers 两数相加
📌 两个非空链表表示两个逆序存储的数字（如 2→4→3 表示 342），求和并返回同样格式的链表。
🔍 解题分析
核心思路：模拟竖式加法。逐位相加，维护进位 carry。注意处理最后可能的进位。
✅ 完整 Java 实现
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode cur = dummy;
int carry = 0; // 进位
while (l1 != null || l2 != null || carry != 0) {
int sum = carry;
if (l1 != null) {
sum += l1.val;
l1 = l1.next;
}
if (l2 != null) {
sum += l2.val;
l2 = l2.next;
}
cur.next = new ListNode(sum % 10); // 当前位
carry = sum / 10; // 进位
cur = cur.next;
}
return dummy.next;
}⏱ 复杂度分析
- 时间复杂度：O(max(m, n))
- 空间复杂度：O(max(m, n))，新链表
💡 记忆口诀
“进位 carry 随身带，逐位相加不用怕”
19. Remove Nth Node From End of List 删除链表倒数第 N 个结点
📌 删除链表倒数第 n 个节点。如
[1,2,3,4,5], n=2→[1,2,3,5]
🔍 解题分析
核心思路：双指针间隔 n。fast 先走 n 步，然后 fast 和 slow 一起走。fast 到末尾时，slow 正好在倒数第 n 个节点的前一个位置，方便删除。
✅ 完整 Java 实现
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode fast = dummy, slow = dummy;
// fast 先走 n+1 步（让 slow 停在待删节点的前一个）
for (int i = 0; i <= n; i++) {
fast = fast.next;
}
// fast 和 slow 一起走到 fast 到末尾
while (fast != null) {
fast = fast.next;
slow = slow.next;
}
// slow.next 就是要删的节点
slow.next = slow.next.next;
return dummy.next;
}⏱ 复杂度分析
- 时间复杂度：O(n)
- 空间复杂度：O(1)
💡 记忆口诀
“fast 先跑 n 步，两人再同跑，slow 就到了要删的前一个”
24. Swap Nodes in Pairs 两两交换链表中的节点
📌 每两个相邻节点交换。如
1→2→3→4→2→1→4→3。不能直接改值。
🔍 解题分析
核心思路：三个指针 pre → node1 → node2。交换 node1 和 node2，然后 pre 前进两步。
✅ 完整 Java 实现
public ListNode swapPairs(ListNode head) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode pre = dummy; // pre 指向每对的前一个节点
while (pre.next != null && pre.next.next != null) {
ListNode node1 = pre.next;
ListNode node2 = node1.next;
// 交换：pre → node2 → node1 → node2.next
pre.next = node2;
node1.next = node2.next;
node2.next = node1;
// pre 前进到下一对的前一个位置
pre = node1;
}
return dummy.next;
}⏱ 复杂度分析
- 时间复杂度：O(n)
- 空间复杂度：O(1)
💡 记忆口诀
“pre 坐镇看 node1 和 node2 交换，换完 pre 跳两步”
25. Reverse Nodes in k-Group K 个一组翻转链表
📌 每 k 个节点一组进行翻转。如
[1,2,3,4,5], k=2→[2,1,4,3,5]（不足 k 个不翻转）
🔍 解题分析
核心思路：
- 先检查剩余节点是否够 k 个，不够就不翻转
- 够的话，反转当前组内的 k 个节点
- 处理好前一组尾 → 当前组头，当前组尾 → 下一组头的连接
类比：就像翻扑克牌，每 k 张翻一次。翻之前先数清楚有没有 k 张。
✅ 完整 Java 实现
public ListNode reverseKGroup(ListNode head, int k) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode pre = dummy; // 上一组的尾节点
while (head != null) {
// 1. 检查剩余节点是否够 k 个
ListNode tail = pre;
for (int i = 0; i < k; i++) {
tail = tail.next;
if (tail == null) return dummy.next; // 不够 k 个，结束
}
// 2. 翻转当前组 [head, tail]
ListNode nextGroupHead = tail.next; // 下一组的头
ListNode[] reversed = reverseRange(head, tail);
// 3. 连接：pre → 新头，新尾 → 下一组头
pre.next = reversed[0];
reversed[1].next = nextGroupHead;
// 4. pre 和 head 前进到下一组
pre = reversed[1];
head = nextGroupHead;
}
return dummy.next;
}
// 翻转从 head 到 tail 的链表段，返回 [新头, 新尾]
private ListNode[] reverseRange(ListNode head, ListNode tail) {
ListNode pre = tail.next; // 反转后 head 要指向 tail.next
ListNode cur = head;
while (pre != tail) {
ListNode nxt = cur.next;
cur.next = pre;
pre = cur;
cur = nxt;
}
return new ListNode[]{tail, head}; // 反转后 tail 是新头，head 是新尾
}⏱ 复杂度分析
- 时间复杂度：O(n)
- 空间复杂度：O(1)
💡 记忆口诀
“先数够 K 个，再翻这一段，首尾接好继续走”
138. Copy List with Random Pointer 随机链表的复制
📌 链表节点除 next 指针外，还有一个 random 指针指向任意节点或 null。深拷贝这个链表。
🔍 解题分析
方法一：HashMap 映射（推荐面试先讲）
- 第一遍：创建新节点，建立
oldNode → newNode的映射 - 第二遍：根据映射设置新节点的 next 和 random
方法二：节点插入法（O(1) 空间）
- 在每个原节点后面插入新节点（A→A’→B→B’→C→C’）
- 设置 random：
A'.random = A.random.next - 拆分链表
✅ 完整 Java 实现
// 方法一：HashMap（清晰易懂，面试推荐）
public Node copyRandomList(Node head) {
if (head == null) return null;
// 第一遍：创建新节点 + 建立映射
Map<Node, Node> map = new HashMap<>();
Node cur = head;
while (cur != null) {
map.put(cur, new Node(cur.val));
cur = cur.next;
}
// 第二遍：设置 next 和 random
cur = head;
while (cur != null) {
Node newNode = map.get(cur);
newNode.next = map.get(cur.next); // cur.next 可能为 null，map.get(null)=null
newNode.random = map.get(cur.random); // cur.random 可能为 null
cur = cur.next;
}
return map.get(head);
}
// 方法二：O(1) 空间
public Node copyRandomList_O1(Node head) {
if (head == null) return null;
// 1. 插入新节点：A → A' → B → B' → C → C'
Node cur = head;
while (cur != null) {
Node newNode = new Node(cur.val);
newNode.next = cur.next;
cur.next = newNode;
cur = newNode.next;
}
// 2. 设置 random 指针
cur = head;
while (cur != null) {
if (cur.random != null) {
cur.next.random = cur.random.next;
}
cur = cur.next.next;
}
// 3. 拆分链表
Node dummy = new Node(0);
Node copyCur = dummy;
cur = head;
while (cur != null) {
copyCur.next = cur.next; // A'
copyCur = copyCur.next;
cur.next = cur.next.next; // 恢复原链表 A → B
cur = cur.next;
}
return dummy.next;
}⏱ 复杂度分析
- 时间复杂度：O(n)
- 空间复杂度：HashMap 方法 O(n)，节点插入法 O(1)
💡 记忆口诀
“先映射新旧，再穿针引线”
23. Merge k Sorted Lists 合并 K 个升序链表
📌 合并 k 个有序链表为一个。如
[[1,4,5],[1,3,4],[2,6]]→[1,1,2,3,4,4,5,6]
🔍 解题分析
方法一：归并法（推荐）
- 两两合并，使用 21 题的 mergeTwoLists
- 分治思想：第一轮 k/2 对，第二轮 k/4 对……
方法二：堆（见 14-堆）
✅ 完整 Java 实现
// 归并法
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0) return null;
return mergeSort(lists, 0, lists.length - 1);
}
// 分治合并 lists[left..right]
private ListNode mergeSort(ListNode[] lists, int left, int right) {
if (left == right) return lists[left];
int mid = left + (right - left) / 2;
ListNode l1 = mergeSort(lists, left, mid);
ListNode l2 = mergeSort(lists, mid + 1, right);
return mergeTwoLists(l1, l2);
}
// 复用 21 题
private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode cur = dummy;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
cur.next = l1;
l1 = l1.next;
} else {
cur.next = l2;
l2 = l2.next;
}
cur = cur.next;
}
cur.next = (l1 != null) ? l1 : l2;
return dummy.next;
}⏱ 复杂度分析
- 时间复杂度：O(N log k)，N 为总节点数，k 为链表数
- 空间复杂度：O(log k)（递归栈）
💡 记忆口诀
“两两合并用分治，logK 层每层 N”
146. LRU Cache LRU 缓存
📌 设计并实现 LRU（最近最少使用）缓存。get 和 put 需 O(1)。
🔍 解题分析
核心数据结构：HashMap + 双向链表。
- HashMap：key → 链表节点，实现 O(1) 查找
- 双向链表：维护访问顺序，头部是最近使用的，尾部是最久未使用的
操作：
get(key)：HashMap 查节点 → 把节点移到链表头 → 返回值put(key, value)：- 如果 key 存在：更新值，移到链表头
- 如果 key 不存在：新建节点放链表头；若超容量，删掉链表尾节点
类比：就像手机后台应用。最近用的排在最前面；内存不够时，杀最后面的进程。
✅ 完整 Java 实现
class LRUCache {
// 双向链表节点
private static class Node {
int key, value;
Node prev, next;
Node(int key, int value) {
this.key = key;
this.value = value;
}
}
private final int capacity;
private final Map<Integer, Node> map;
private final Node head; // 哨兵头（最近使用）
private final Node tail; // 哨兵尾（最久未使用）
public LRUCache(int capacity) {
this.capacity = capacity;
this.map = new HashMap<>();
// 初始化哨兵节点
head = new Node(0, 0);
tail = new Node(0, 0);
head.next = tail;
tail.prev = head;
}
public int get(int key) {
if (!map.containsKey(key)) return -1;
Node node = map.get(key);
moveToHead(node); // 刚访问过，移到队头
return node.value;
}
public void put(int key, int value) {
if (map.containsKey(key)) {
Node node = map.get(key);
node.value = value;
moveToHead(node);
} else {
Node node = new Node(key, value);
map.put(key, node);
addToHead(node);
if (map.size() > capacity) {
// 移除最久未使用的（队尾前一个）
Node removed = removeTail();
map.remove(removed.key);
}
}
}
// ---- 双向链表基本操作 ----
private void addToHead(Node node) {
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
}
private void removeNode(Node node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
private void moveToHead(Node node) {
removeNode(node);
addToHead(node);
}
private Node removeTail() {
Node last = tail.prev;
removeNode(last);
return last;
}
}⏱ 复杂度分析
- 时间复杂度：get 和 put 均为 O(1)
- 空间复杂度：O(capacity)
💡 记忆口诀
“HashMap 管查找，双向链表管顺序，用了就放最前面，满了就删最后面”