链表的应用——真题归纳与解读|算法篇
链表结构相对数组、字符串来说，稍微有那么一些些复杂，所以针对链表的真题戏份也相对比较多。 前面咱们说过，数组、字符串若想往难了出，那一定是要结合一些超越数据结构本身的东西——比如排序算法、二分思想、动态规划思想等等。因此，这部分对应的难题、综合题，我们需要等知识体系完全构建起来之后，在真题训练环节重新复盘。
但是链表可不一样了。如果说在命题时，数组和字符串的角色往往是“算法思想的载体”，那么链表本身就可以被认为是“命题的目的”。单在真题归纳解读环节，我们能讲的技巧、能做的题目已经有很多。结合实际面试中的命题规律，我把这些题目分为以下三类：
- 链表的处理：合并、删除等（删除操作画个记号，重点中的重点！）
- 链表的反转及其衍生题目
- 链表成环问题及其衍生题目
本节我们就以链表的处理为切入点，一步一步走进链表的世界。
# 链表的合并
30 秒速记
- 两条输入链都有序，比较当前头结点，把较小者接到结果尾部并推进对应指针
dummy固定结果入口，tail始终指向已合并前缀最后一个结点，避免单独处理第一个结点- 一侧耗尽后，另一侧剩余部分本来有序，可以整段接上，不必逐结点复制
- 时间
O(m+n)、迭代辅助空间O(1)；实现复用并重连原结点，会改变输入链结构 - 相等值取左还是取右决定稳定性；若不能修改输入，需要创建新结点并承担
O(m+n)空间
合并两条有序链表时，持续比较当前头结点，把较小的结点接到结果链表尾部即可。 dummy 用来固定结果入口，tail 始终指向已合并部分的末尾，因此不用单独处理第一个结点。一条链表耗尽后，另一条剩余部分本身有序，可以直接整体接上，时间复杂度是 O(m+n)，辅助空间是 O(1)。这种写法会重连原结点；如果输入链不能被修改，就需要复制结点并使用 O(m+n) 空间。
function mergeTwoLists(left, right) {
const dummy = { next: null }
let tail = dummy
while (left !== null && right !== null) {
if (left.val <= right.val) {
tail.next = left
left = left.next
} else {
tail.next = right
right = right.next
}
tail = tail.next
}
tail.next = left ?? right
return dummy.next
}
循环前，dummy.next..tail 已经包含两条链中被消费的最小元素且保持有序；left、right 分别指向未处理部分最小值。每轮至少推进一个指针，必然终止。该版本会重连原结点；如果其他调用方仍持有旧链并假设其结构不变，应复制结点或明确转移所有权。
真题描述：将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有结点组成的。
示例：
输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4
思路分析
做链表处理类问题，大家要把握住一个中心思想——处理链表的本质，是处理链表结点之间的指针关系。
这道题也不例外，我们先来看看处理前两个链表的情况：
- 两个链表如果想要合并为一个链表，我们恰当地补齐双方之间结点 next 指针的指向关系，就能达到目的。
- 如果这么说仍然让你觉得抽象，那么大家不妨把图上的6个结点想象成6个扣子：现在的情况是，6个扣子被分成了两拨，各自由一根线把它们穿起来。而我们的目的是让这六个扣子按照一定的顺序，串到一根线上去。这时候需要咱们做的就是一个穿针引线的活儿，现在线有了，咱缺的是一根针
这根针每次钻进扣子眼儿之前，要先比较一下它眼前的两个扣子，选择其中值较小的那个，优先把它串进去。一次串一个，直到所有的扣子都被串进一条线为止（下图中红色箭头表明穿针的过程与方向）：
同时我们还要考虑 l1 和 l2 两个链表长度不等的情况：若其中一个链表已经完全被串进新链表里了，而另一个链表还有剩余结点，考虑到该链表本身就是有序的，我们可以直接把它整个拼到目标链表的尾部。
编码实现
/**
* @param {ListNode} l1
* @param {ListNode} l2
* @return {ListNode}
*/
const mergeTwoLists = function(l1, l2) {
// 定义头结点，确保链表可以被访问到
let head = new ListNode()
// cur 这里就是咱们那根“针”
let cur = head
// “针”开始在 l1 和 l2 间穿梭了
while(l1 && l2) {
// 如果 l1 的结点值较小
if(l1.val<=l2.val) {
// 先串起 l1 的结点
cur.next = l1
// l1 指针向前一步
l1 = l1.next
} else {
// l2 较小时，串起 l2 结点
cur.next = l2
// l2 向前一步
l2 = l2.next
}
// “针”在串起一个结点后，也会往前一步
cur = cur.next
}
// 处理链表不等长的情况
cur.next = l1!==null?l1:l2
// 返回起始结点
return head.next
};
面试官追问
追问 1候选人说合并后的链表是“新的”，所以实现一定不会修改两条输入链；面对 tail.next = left 这行代码，你会怎么反驳？
“新的有序链表”不代表结点必须新建，这段实现复用原结点并改写它们的 next 关系。调用方若仍按旧结构持有输入链，观察到的连接会发生变化；需要保留原链时必须复制结点，代价是额外的线性空间。
追问 2订单页面合并两条已按时间排序的链表，相同时间的订单还要保持左侧数据源优先，比较条件该写 < 还是 <=？
应使用 <=，相等时先连接左链结点，才能维持约定的跨数据源稳定顺序。改成 < 仍能保证键值有序，却会让右链相等元素排在前面；结点携带来源或创建次序时，这种差异会影响业务展示。
追问 3接口从合并两条有序链改成合并 k 条有序链，继续逐条调用 mergeTwoLists 有什么取舍？
逐条合并实现简单并能复用现有代码，但早期已合并出的长链会被反复遍历，链数增大时不够均衡。可按两两分治合并，或用最小堆维护各链表头；后者需要额外结构，具体选择还取决于链数和依赖约束。
追问 4线上任务合并时 CPU 持续占用且请求不返回，采样显示 while (left !== null && right !== null) 一直运行，你会优先排查什么？
优先检查输入链是否成环，以及结点的 next 是否在进入函数前已被并发或其他逻辑破坏；合法无环输入下，每轮必然推进一个指针。对不可信入口可先做环检测或设置访问上限，但会增加遍历成本或引入截断策略。
追问 5内存敏感的服务要求低额外空间，而另一个调用方要求输入链完全不可变，两项约束冲突时你怎样定接口？
复用结点可保持常量级辅助空间，但必然重连原链；复制结点能保护输入结构，却需要与结点数量同阶的新内存。接口应明确“消费输入”还是“只读输入”，无法同时满足时不能把所有权变化藏在实现细节里。
# 链表结点的删除
30 秒速记
- 题目要求有序链表“每个值保留一个”，重复值必然连续，只需比较
current与current.next - 相等时执行
current.next = current.next.next，但不能移动 current，以便继续删除第三、第四个副本 - 不相等时才能推进 current；这条分支决定循环是否既不漏删又能终止
- 时间
O(n)、辅助空间O(1)，原地修改链表；空链和单结点自然返回 - 若输入无序，相同值不连续，该算法不正确，需要哈希集合或先排序，并承担相应代价
有序链表中的重复值连续出现，所以比较 current 和 current.next 就能完成去重。 两者相等时让 current.next 指向下下个结点，但不要移动 current，否则像 1→1→1 这样的连续重复可能漏删。只有值不相等时才向后推进，这样每个结点最多处理一次，时间复杂度是 O(n)，辅助空间是 O(1)。该方法会原地修改链表，而且只适用于有序输入；无序链表需要额外的哈希集合或先排序。
原文代码的关键不是 while 本身，而是相等分支不推进 cur。输入 1→1→1 时，第一次删掉第二个 1 后，当前结点还要与新的后继继续比较：
function keepOneDuplicate(head) {
let current = head
while (current?.next) {
if (current.val === current.next.val) current.next = current.next.next
else current = current.next
}
return head
}
每个被保留或删除的结点最多处理一次，时间 O(n)。被跳过结点在没有其他引用时会由垃圾回收处理；若结点持有文件、订阅等外部资源，链表断开不会自动释放那些资源，需要业务层显式清理。
我们先来看一道基础题目：
真题描述：给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
示例 1:
- 输入: 1->1->2
- 输出: 1->2
示例 2:
- 输入: 1->1->2->3->3
- 输出: 1->2->3
思路分析
链表的删除是一个基础且关键的操作，我们在数据结构部分就已经对该操作的编码实现进行过介绍，这里直接复用大家已经学过的删除能力，将需要删除的目标结点的前驱结点 next 指针往后指一格：
编码实现
/**
* @param {ListNode} head
* @return {ListNode}
*/
const deleteDuplicates = function(head) {
// 设定 cur 指针，初始位置为链表第一个结点
let cur = head;
// 遍历链表
while(cur != null && cur.next != null) {
// 若当前结点和它后面一个结点值相等（重复）
if(cur.val === cur.next.val) {
// 删除靠后的那个结点（去重）
cur.next = cur.next.next;
} else {
// 若不重复，继续遍历
cur = cur.next;
}
}
return head;
};
大家不要小看了这么一道简简单单的基础题目，在实际面试中，下不了笔的、写不囫囵的、写了跑不起来的，大有人在。
一道题之所以能够成为面试题，一定有其考察意义在。拿这道题来说，既能考察你链表的遍历（while循环），又能考察你链表的 CRUD 中最热门的删除操作，候选人做这道题的情况，一定程度上可以反馈其基本功的扎实度。做对了是正常，如果做不对，那么在算法和数据结构这个考察环节，你的处境就有点危险了。
