链表
2026/4/10大约 20 分钟常用算法题链表
本章题海战术
| 典型例题 | leetcode题目 | leetcode链接 |
|---|---|---|
| 反转链表 | leetcode 206 | https://leetcode.cn/problems/reverse-linked-list/description/ |
| 反转链表 II | leetcode 92 | https://leetcode.cn/problems/reverse-linked-list-ii/description/ |
| 环形链表 | leetcode 141 | https://leetcode.cn/problems/linked-list-cycle/description/ |
| 环形链表 II | leetcode 142 | https://leetcode.cn/problems/linked-list-cycle-ii/description/ |
| 合并两个有序链表 | leetcode 21 | https://leetcode.cn/problems/merge-two-sorted-lists/description/ |
| 合并 K 个升序链表 | leetcode 23 | https://leetcode.cn/problems/merge-k-sorted-lists/description/ |
| 删除链表的倒数第N个结点 | leetcode 19 | https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description/ |
| 相交链表 | leetcode 160 | https://leetcode.cn/problems/intersection-of-two-linked-lists/description/ |
| LRU 缓存 | leetcode 146 | https://leetcode.cn/problems/lru-cache/description/ |
| 链表的中间结点 | leetcode 876 | https://leetcode.cn/problems/middle-of-the-linked-list/description/ |
| 删除排序链表中的重复元素 | leetcode 83 | https://leetcode.cn/problems/remove-duplicates-from-sorted-list/description/ |
链表
链表基础特性 💡
链表是物理存储非连续的线性数据结构，通过指针将零散的内存节点串联起来，每个节点包含「数据域 + 指针域」。面试最常考单链表和双向链表。
1. 结构示意图
单链表（仅后继指针）：
双向链表（前驱 + 后继指针）：
2. 链表 vs 数组 核心对比
| 对比维度 | 数组 | 链表 |
|---|---|---|
| 存储方式 | 连续内存空间 | 零散内存，指针串联 |
| 随机访问 | O (1) 按下标直接访问 | O (n) 必须从头遍历 |
| 插入 / 删除 | O (n) 需要批量搬移元素 | O (1) 仅修改指针（找到目标后） |
| 空间特性 | 固定大小，扩容成本高 | 动态扩容，无预分配浪费 |
| 适用场景 | 数据量固定、频繁随机访问 | 数据量不定、频繁增删操作 |
高频必考算法题（Java 实现）🚀
链表题核心考察指针操作，套路性很强，我整理了 6 道最高频的题目，覆盖 90% 的面试场景：
1. 反转单链表(leetcode 206)（热度 ⭐⭐⭐⭐⭐）
题目：给定单链表头节点，反转链表并返回新的头节点。
核心思路：双指针迭代法，用prev和curr两个指针逐个翻转指针方向，空间复杂度 O (1)，最稳妥的面试写法。
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode next = curr.next; // 先保存下一个节点，防止断链
curr.next = prev; // 翻转当前节点指针
prev = curr; // prev 后移
curr = next; // curr 后移
}
return prev; // 循环结束prev就是新头节点
}⚠️ 面试踩坑：必须先存后继节点再改指针；递归写法也能实现，但有栈溢出风险，面试优先写迭代版。
2. 判断链表是否有环(leetcode 141)（热度 ⭐⭐⭐⭐⭐）
题目：判断一个单链表中是否存在环。
核心思路：快慢指针（龟兔赛跑），快指针每次走 2 步，慢指针每次走 1 步；有环则两指针必然相遇，无环则快指针先走到 null。
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;
}💡 高频追问：求环的入口点 → 相遇后将 slow 移回头节点，两指针同速前进，再次相遇的位置就是环入口。
3. 合并两个有序链表(leetcode 21)（热度 ⭐⭐⭐⭐）
题目：将两个升序链表合并为一个新的升序链表并返回。
核心思路：虚拟头节点 + 双指针，类似归并排序的 merge 过程，逐个比较节点值，将更小的节点接在结果链表后。
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(-1); // 虚拟头节点，规避头节点边界问题
ListNode curr = dummy;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
curr.next = l1;
l1 = l1.next;
} else {
curr.next = l2;
l2 = l2.next;
}
curr = curr.next;
}
curr.next = l1 == null ? l2 : l1; // 拼接剩余非空链表
return dummy.next;
}✅ 通用技巧：涉及头节点可能被修改的题目，优先用虚拟头节点，大幅减少边界判断。
4. 删除链表倒数第 N 个节点(leetcode 19)（热度 ⭐⭐⭐⭐）
题目：删除单链表的倒数第 N 个节点，返回链表头节点。
核心思路：快慢指针 + 虚拟头节点；快指针先走 N+1 步，之后两指针同速前进，快指针到末尾时，慢指针正好停在待删节点的前驱位置。
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(-1, head);
ListNode fast = dummy, slow = dummy;
for (int i = 0; i <= n; i++) fast = fast.next; // 快指针先走n+1步
while (fast != null) {
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next; // 跳过待删除节点
return dummy.next;
}⚠️ 面试踩坑：不用虚拟头节点的话，删除头节点时会触发空指针异常。
5. 相交链表(leetcode 160)（热度 ⭐⭐⭐⭐）
题目：找出两个单链表相交的起始节点，不相交则返回 null。
核心思路：双指针浪漫解法；两指针分别从两个链表头出发，走到末尾就切换到另一个链表头继续走，有交点则必然相遇，无交点则最终都指向 null。
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) return null;
ListNode pA = headA, pB = headB;
while (pA != pB) {
pA = pA == null ? headB : pA.next;
pB = pB == null ? headA : pB.next;
}
return pA;
}💡 原理：两个指针走过的总路程都是「A 链表长度 + B 链表长度」，因此一定会在交点处相遇。
6. LRU 缓存机制(leetcode 146)（热度 ⭐⭐⭐）
题目：设计实现 LRU 缓存，支持get和put操作，时间复杂度要求 O (1)。
核心思路：哈希表 + 双向链表组合实现；哈希表存 key 到节点的映射保证 O (1) 查询，双向链表按访问顺序维护节点（最近访问放头部，最久未访问在尾部），容量满时删除尾部节点。
class LRUCache {
class DLinkedNode { int key, value; DLinkedNode prev, next; }
private Map<Integer, DLinkedNode> cache = new HashMap<>();
private int size, capacity;
private DLinkedNode head, tail; // 头尾虚拟节点
// 核心原子操作：添加到头节点、删除指定节点、移到头部、删除尾部节点
}✅ 考点本质：考察双向链表的精细化增删操作，以及数据结构组合设计的思路。
链表题通用解题套路 ✅
面试做链表题，记住这 4 个技巧，能解决 90% 的场景：
- 虚拟头节点：删除(leetcode 19)、反转(leetcode 206)、合并(leetcode 21)等可能修改头节点的题目，优先加虚拟头规避边界空指针。
- 快慢指针：环检测(leetcode 141)、找中点(leetcode 876)、倒数第 N 个节点(leetcode 19)，都是快慢指针的经典应用。
- 先存后继再改指针：修改
next指针前，一定先保存原后继节点，防止断链。 - 画图辅助：指针操作容易混乱，面试时可以在草稿纸上画节点和指针走向，大幅降低出错概率。
核心代码与技术亮点拆解 🎯
我整理了每道高频题的面试最优实现，每段代码都标注了对应的技术加分点，都是大厂面试的得分关键：
1. 反转单链表 - 迭代最优版
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode next = curr.next; // 暂存后继节点，防止断链
curr.next = prev; // 翻转当前节点指针
prev = curr; // 双指针同步后移
curr = next;
}
return prev;
}✅ 技术亮点
- 原地修改节点指针，空间复杂度 O (1)，远优于递归法的 O (n) 栈空间
- 天然兼容空链表、单节点链表等所有边界场景，无需额外 if 判断
- 三步操作逻辑固定无冗余，面试手写零出错率，是面试官公认的标准写法
2. 环形链表 II（求环入口）(leetcode 142) - 数学推导最优解
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) {
slow = head; // 慢指针重置回链表起点
while (slow != fast) {
slow = slow.next;
fast = fast.next; // 双指针同速前进
}
return slow;
}
}
return null;
}✅ 技术亮点
- 基于快慢指针路程差公式推导实现，无需额外哈希存储，空间复杂度 O (1)
- 一次遍历完成「判环 + 找入口」，时间复杂度 O (n)，是该题的理论最优解
- 面试时能讲清「头节点到入口的距离 = 相遇点到入口的距离」的推导过程，直接拉开和普通背题选手的差距
3. 合并两个有序链表(leetcode 21) - 虚拟头节点优雅版
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(-1); // 虚拟头节点
ListNode curr = dummy;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
curr.next = l1;
l1 = l1.next;
} else {
curr.next = l2;
l2 = l2.next;
}
curr = curr.next;
}
curr.next = l1 == null ? l2 : l1; // 一次性拼接剩余节点
return dummy.next;
}✅ 技术亮点
- 虚拟头节点统一了「头节点赋值」和「中间节点拼接」的逻辑，彻底消除头节点边界判断
- 代码结构和归并排序 merge 逻辑完全对齐，可读性和可维护性极强
- 尾部一次性拼接剩余链表，避免循环冗余判断，代码更简洁高效
4. LRU 缓存(leetcode 146) - 工业级标准实现
class LRUCache {
// 双向链表节点
class DLinkedNode {
int key, value;
DLinkedNode prev, next;
public DLinkedNode() {}
public DLinkedNode(int key, int value) {
this.key = key;
this.value = value;
}
}
private Map<Integer, DLinkedNode> cacheMap = new HashMap<>();
private int size;
private int capacity;
private DLinkedNode head, tail; // 虚拟头尾节点
public LRUCache(int capacity) {
this.size = 0;
this.capacity = capacity;
head = new DLinkedNode();
tail = new DLinkedNode();
head.next = tail;
tail.prev = head;
}
// 查询缓存
public int get(int key) {
DLinkedNode node = cacheMap.get(key);
if (node == null) return -1;
moveToHead(node); // 访问后移到链表头部，标记为最近使用
return node.value;
}
// 写入缓存
public void put(int key, int value) {
DLinkedNode node = cacheMap.get(key);
if (node == null) {
DLinkedNode newNode = new DLinkedNode(key, value);
cacheMap.put(key, newNode);
addToHead(newNode);
size++;
// 超出容量，删除最久未使用的尾部节点
if (size > capacity) {
DLinkedNode tailNode = removeTail();
cacheMap.remove(tailNode.key);
size--;
}
} else {
node.value = value;
moveToHead(node);
}
}
// 原子操作1：添加节点到链表头部
private void addToHead(DLinkedNode node) {
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
}
// 原子操作2：删除指定节点
private void removeNode(DLinkedNode node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
// 原子操作3：将节点移动到头部
private void moveToHead(DLinkedNode node) {
removeNode(node);
addToHead(node);
}
// 原子操作4：删除尾部节点
private DLinkedNode removeTail() {
DLinkedNode res = tail.prev;
removeNode(res);
return res;
}
}✅ 技术亮点
- 「哈希表 + 双向链表」经典组合设计，get/put 操作均为 O (1) 时间复杂度，满足工业级性能要求
- 虚拟头尾节点设计，彻底避免增删操作时的空指针边界判断，代码鲁棒性拉满
- 拆分原子操作，单一职责原则，避免重复代码，是大厂开发的标准编码风格
技术难点与解决方案汇总 🧩
我把链表算法面试中最容易踩坑的技术难点，整理成了对应解决方案和面试加分话术：
| 技术难点描述 | 问题影响 | 解决方案 | 面试加分回答 |
|---|---|---|---|
| 修改 next 指针时未暂存后继节点，导致链表断链 | 后续节点全部丢失，遍历直接触发空指针异常 | 改指针前，必须先用临时变量保存当前节点的原 next 节点 | 「链表操作的核心原则是：先存后改，宁多存不多改」 |
| 头节点可能被修改 / 删除时，直接操作原头引发边界错误 | 删除头节点、合并链表首节点时，边界处理繁琐，极易出现 NPE | 统一使用虚拟头节点 (dummy)，所有操作从虚拟头开始，最终返回 dummy.next | 「只要头节点可能变化，我都会先加虚拟头，用一套逻辑处理所有场景」 |
| 环形链表(leetcode 141)入口点原理说不清，被判定为纯背代码 | 面试官追问原理直接卡壳，算法理解深度不达标 | 掌握数学推导：设头到入口距离 a，环长 b；相遇时 fast 路程 = 2*slow 路程，推导得 a = 相遇点到入口的距离 | 「我可以从快慢指针的路程差推导入口点公式，不是纯背代码」 |
| 删除倒数第 N 个节点(leetcode 19)时，N 等于链表长度（删头节点）场景失效 | 慢指针定位错误，出现空指针或删错节点 | 快指针先走 N+1 步，且配合虚拟头节点起步，保证慢指针最终停在待删节点的前驱位置 | 「我统一让快慢指针从虚拟头出发，快指针多走一步，完美兼容删头场景」 |
| LRU(leetcode 146) 双向链表指针操作繁琐，容易改反 / 漏改 | 链表结构错乱，节点增删出现逻辑 bug | 拆分「添加到头、删除节点、移动到头、删尾部」四个原子方法，上层业务只调用原子方法 | 「我会把双向链表的操作拆成原子方法，单一职责，避免重复代码和指针改错」 |
| 相交链表(leetcode 160)双指针法原理理解不透彻 | 被追问为什么不会死循环、为什么一定相遇时答不上 | 明确总路程：两个指针都走了 len (A)+len (B)，有交点则在交点相遇，无交点则同时走到 null | 「两个指针走过的总路径长度完全相等，所以要么在交点相遇，要么同时指向 null 退出」 |
真实面试模拟
好的，那我们开始。今天主要考察链表，准备好了吗？😊
真实面试模拟
面试官：
先热个身，反转一个单链表(leetcode 206)，你来说说思路，不用马上写代码。
候选人：
👌 核心就是掰指针。我用三个指针 prev、curr、next，遍历时把 curr.next 指向 prev，然后三个指针整体后移，直到 curr 为空，prev 就是新头。
面试官：
不错，能画一下吗？
候选人：（拿笔在白板上画）
面试官：
清楚。直接写一下代码，边界条件怎么处理？
候选人：
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode nextTemp = curr.next; // 先存下一个
curr.next = prev; // 反转
prev = curr; // 前移
curr = nextTemp;
}
return prev;
}面试官：
时间复杂度 O(n)，空间 O(1)。递归实现你清楚吗？
候选人：
递归的话，先递到最后一个节点作为新头，回溯时让 head.next.next = head，再断开 head.next = null。
public ListNode reverseListRecursive(ListNode head) {
if (head == null || head.next == null) return head;
ListNode newHead = reverseListRecursive(head.next);
head.next.next = head;
head.next = null;
return newHead;
}面试官：
好，下一题。合并两个升序链表(leetcode 21)。
候选人：
用个哑节点 dummy，然后比较 l1 和 l2 的 val，小的接到后面，哪个没完就把剩下的整体接上。
面试官：
dummy 节点有什么用？
候选人：
避免处理头节点为空的特殊情况，让代码统一，最后返回 dummy.next 就行。
面试官：
写一下迭代代码。
候选人：
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(-1);
ListNode tail = dummy;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
tail.next = l1;
l1 = l1.next;
} else {
tail.next = l2;
l2 = l2.next;
}
tail = tail.next;
}
tail.next = (l1 != null) ? l1 : l2;
return dummy.next;
}面试官：
递归你会怎么写？
候选人：
public ListNode mergeTwoListsRecursive(ListNode l1, ListNode l2) {
if (l1 == null) return l2;
if (l2 == null) return l1;
if (l1.val <= l2.val) {
l1.next = mergeTwoListsRecursive(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoListsRecursive(l1, l2.next);
return l2;
}
}面试官：
ok。接下来判断链表有没有环(leetcode 141)。
候选人：
🐢🐇 快慢指针，慢的走一步，快的走两步，如果有环他俩一定会相遇。
public boolean hasCycle(ListNode head) {
if (head == null) return false;
ListNode slow = head, fast = head.next;
while (fast != null && fast.next != null) {
if (slow == fast) return true;
slow = slow.next;
fast = fast.next.next;
}
return false;
}面试官：
那如果找到环的入口呢(leetcode 142)？
候选人：
相遇后，把一个指针放回头节点，两个指针每次都走一步，再次相遇的点就是入口。可以画个图：
头到入口距离 a，入口到相遇点 b，相遇点再到入口 c，环长 b+c。因为快指针路程是慢指针两倍，推导出 a=c。
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 ptr = head;
while (ptr != slow) {
ptr = ptr.next;
slow = slow.next;
}
return ptr;
}
}
return null;
}面试官：
嗯，这个推导很关键。下一题，删除链表的倒数第 N 个节点(leetcode 19)，要求一趟扫描。
候选人：
还是双指针。
策略：
first指针先向前走 n 步- 然后
second指针从哑节点出发，与first保持固定间隔同步前进 - 当
first走到末尾（null）时，second刚好停在待删除节点的前驱位置
用简单示意图表示（假设链表 1→2→3→4→5，删除倒数第 2 个节点）：
初始:
first → 1 → 2 → 3 → 4 → 5 → null
second(dummy) ↑
① first 先走 2 步:
first → 3 → 4 → 5 → null
second(dummy) ↑
② first, second 一起走，直到 first 到达 null:
first → null
second → 3 (此时 second 指向节点 3，它的下一个节点 4 就是要删除的)
③ 执行删除: second.next = second.next.next
链表变为 1→2→3→5这个过程中 dummy 节点保证了即使要删除头节点，second 也能正确指向它的前驱。
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0, head);
ListNode first = head;
ListNode second = dummy;
for (int i = 0; i < n; i++) first = first.next;
while (first != null) {
first = first.next;
second = second.next;
}
second.next = second.next.next;
return dummy.next;
}面试官：
好。最后一道，两个链表找相交起点(leetcode 160)，O(n) 时间 O(1) 空间。
候选人：
💘 浪漫相遇。pA 走 A 链表，走完转到 B 链表头；pB 走 B 链表，走完转到 A 链表头。如果相交，他们走过的总路程会相等，在交点相遇；不相交最后都走向 null。
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) return null;
ListNode pA = headA, pB = headB;
while (pA != pB) {
pA = (pA == null) ? headB : pA.next;
pB = (pB == null) ? headA : pB.next;
}
return pA;
}面试官：
很不错，今天这几道题你回答得很清晰。我稍微总结一下：
链表题万变不离其宗，核心就三个技巧：双指针（快慢/前后）、dummy 节点、递归/迭代。面试常考的题型都在这张表里了：
| 类型 | 经典题 | 关键技巧 |
|---|---|---|
| 反转 | 反转整个链表(leetcode 206) / 区间反转(leetcode 92) | 三指针 / 头插法 |
| 合并 | 两个有序链表(leetcode 21) / 合并K个(leetcode 23) | 归并 / 堆 |
| 环 | 判断环(leetcode 141) / 找入口(leetcode 142) | 快慢指针 |
| 删除 | 删除倒数第N个(leetcode 19) / 重复节点(leetcode 83) | 双指针，dummy |
| 相交 | 找交点(leetcode 160) | 双指针走两遍 |
💎 核心代码与技术亮点
面试官：
你刚才写的几段代码，有些地方写得挺巧妙的，我帮你整理一下，看看哪些是“加分项”。
1. 反转链表(leetcode 206) —— 三指针迭代法
// 亮点：只用三个指针，原地反转，无额外空间
public ListNode reverseList(ListNode head) {
ListNode prev = null, curr = head;
while (curr != null) {
ListNode nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}✨ 技术亮点：
- 纯粹的指针操作，空间复杂度 O(1)
- 临时变量
nextTemp避免断链，是链表操作的基本素养 - 递归写法
head.next.next = head体现了对“指针反转”的另一种理解
2. 合并两个有序链表(leetcode 21) —— dummy 节点 + 尾插法
// 亮点：dummy 节点统一空头处理，tail 指针跟踪尾部
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(-1);
ListNode tail = dummy;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
tail.next = l1;
l1 = l1.next;
} else {
tail.next = l2;
l2 = l2.next;
}
tail = tail.next;
}
tail.next = (l1 != null) ? l1 : l2;
return dummy.next;
}✨ 技术亮点：
dummy节点消灭了“头节点需要特殊处理”的边界地狱tail指针是尾插法的精髓，很多链表的构建题（如两数相加、分区链表）都能复用这个套路
3. 判断环(leetcode 141) & 找入口(leetcode 142) —— 快慢指针的数学之美
// 亮点：相遇后一个指针回头，两个指针等速走，相遇即入口
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 ptr = head;
while (ptr != slow) {
ptr = ptr.next;
slow = slow.next;
}
return ptr;
}
}
return null;
}✨ 技术亮点：
- 不只是会用快慢指针，还能讲清「为什么 a = c」
- 这个思路可以迁移到「寻找重复数」等数组问题
4. 删除倒数第 N 个节点(leetcode 19) —— 前后双指针
// 亮点：first 先走 n 步，second 从 dummy 出发，优雅删除
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0, head);
ListNode first = head, second = dummy;
for (int i = 0; i < n; i++) first = first.next;
while (first != null) {
first = first.next;
second = second.next;
}
second.next = second.next.next;
return dummy.next;
}✨ 技术亮点：
- 又是
dummy节点救命，删除头节点也不用单独判空 - 前后指针错位 n 步，是一类“窗口”问题的通用模板
5. 相交链表(leetcode 160) —— 双指针走两遍
// 亮点：你走过我走的路，我们终究会相遇
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;
}
return pA;
}✨ 技术亮点：
- 消除长度差不用计算长度，用“接续走”的方式自动对齐
- 代码极其简洁，是面试官非常喜欢看到的“聪明的笨办法”
⚠️ 技术难点 & 解决方案
面试官：链表题看起来简单，但其实有几个地方特别容易踩坑，我帮你系统梳理一下。
| 难点 | 具体表现 | 解决方案 |
|---|---|---|
| 断链/野指针 | 修改指针时未保存后续节点，导致链表断开、无法继续遍历 | 永远在改动 next 之前用临时变量保存 curr.next，这是链表操作的第一安全准则 |
| 头节点特殊处理 | 插入、删除时，如果发生在头部，需要单独判断，代码冗余且容易出错 | 引入 dummy 节点，让头节点变得和普通节点一样，最后返回 dummy.next |
| 快慢指针的死循环与空指针 | while(fast != null && fast.next != null) 忘记检查 fast.next，或者起点设置不对导致空指针 | 严格遵循循环条件判断两层；起点可以根据场景选择 head 和 head.next；跑之前先画两步验证一下 |
| 环入口的数学推导容易忘 | 知道快慢指针相遇，但面试时说不清为什么重新走会相遇 | 用公式记：设头到入口 a，入口到相遇点 b，相遇点到入口 c，环长 b+c。由 2(a+b) = a + b + n(b+c) 推出 a = (n-1)(b+c) + c。结论：从头和相遇点同时同速出发，一定在入口相遇。面试时可以边画图边讲，逻辑比记忆更重要 |
| 相交链表的空间优化 | 暴力法用哈希表，空间 O(n)；或者先算长度差再对齐，但代码较长 | 双指针走两遍，利用“总路程相等”消除长度差，空间 O(1) 且代码极简，但需要解释正确性 |
| 递归反转栈溢出 | 递归实现反转链表，在链表很长时可能导致递归栈过深 | 面试时主动说明：生产环境中建议用迭代法，递归更多是为了展示思维。如果一定要递归，可以提一嘴尾递归优化或语言层面的限制 |
| 复制复杂链表（带随机指针） | 遍历时直接拷贝会丢失随机指针指向的节点 | 经典三步走：①插入拷贝节点到原节点后 ②复制 random 指针 ③拆分链表。这题是链表操作的集大成者，如果面试时间充足，可以主动提一下表达你的知识广度 |
📝 最后送你的小抄：
链表题做不出来的时候，先问自己三句话——
- 我有没有用
dummy节点？ - 指针移动前我保存了
next吗？ - 循环条件是不是同时检查了
fast和fast.next？