链表结构相对数组、字符串来说，稍微有那么一些些复杂，所以针对链表的真题戏份也相对比较多。 前面咱们说过，数组、字符串若想往难了出，那一定是要结合一些超越数据结构本身的东西——比如排序算法、二分思想、动态规划思想等等。因此，这部分对应的难题、综合题，我们需要等知识体系完全构建起来之后，在真题训练环节重新复盘。
但是链表可不一样了。如果说在命题时，数组和字符串的角色往往是“算法思想的载体”，那么链表本身就可以被认为是“命题的目的”。单在真题归纳解读环节，我们能讲的技巧、能做的题目已经有很多。结合实际面试中的命题规律，我把这些题目分为以下三类：
- 链表的处理：合并、删除等（删除操作画个记号，重点中的重点！）
- 链表的反转及其衍生题目
- 链表成环问题及其衍生题目
本节我们就以链表的处理为切入点，一步一步走进链表的世界。
# 链表的合并
30 秒速记
- 链表题的本质是改
next指针，合并就是「穿针引线」 - 比两个头，小的接到
tail后面，被选中的那条往前走一步 dummy固定结果入口，不用单独处理第一个结点；返回dummy.next- 一条走完，另一条剩下的整段接上：
tail.next = l1 ?? l2 - 时间
O(m+n)、空间O(1)；复用原结点会改掉输入链，相等时取左边保证稳定
合并两个有序链表就是不停比两个头结点，把小的那个接到结果链尾巴上，直到一条走完，再把另一条剩下的整段接上。 我习惯先建一个 dummy，tail 从它开始，这样第一个结点不用特判，最后返回 dummy.next。整个过程没新建结点，只是改 next，所以空间 O(1)，时间 O(m+n)。有个容易被问的点：这种写法会改掉原来两条链，调用方要是还拿着旧链用就会出事。
// 1->2->4 和 1->3->4
mergeTwoLists(l1, l2) // 1->1->2->3->4->4
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 是在原结点上重新接线，没有新建结点。调用方还要用原链的话，得复制结点，空间变成 O(m+n)。
追问 2相同值要保证左边那条先出来，比较写 < 还是 <=？
<=。相等时先取左链，跨链的相对顺序才稳定。写成 < 结果照样有序，但相等元素会右链在前，结点带着来源信息时就看得出差别。
追问 3扩展到合并 k 条有序链表，一条条往上合可以吗？
能跑，但前面合出来的长链会被反复遍历，最坏 O(kN)。用两两分治合并或者最小堆维护 k 个头，都是 O(N log k)。
追问 4合并时 while 一直不退出，CPU 打满，可能是什么原因？
正常无环输入每轮必推进一个指针，一定会结束。基本是输入链本身成环了，或者别处把 next 改坏了。先用快慢指针判一下环。
追问 5一条走完后，能不能 while 把剩下的结点一个个接上？
能，但没必要。剩下那段本来就有序、本来就连着，tail.next = left ?? right 一行接上，省一个循环。
# 链表结点的删除
30 秒速记
- 有序链表里重复值一定挨着，比
cur和cur.next就够了 - 相等：
cur.next = cur.next.next删掉后一个，cur不动 - 不等：
cur才往后走一步 - 时间
O(n)、空间O(1)，原地改；空链和单结点自然处理 - 无序链表这招失效，要用
Set记见过的值
有序链表去重，就站在当前结点上看下一个：一样就把下一个跳过去，不一样才往前走。 关键就在相等分支不能移动 cur。比如 1->1->1，删掉第二个 1 后，新的下一个还是 1，得接着比。很多人这里写成删完也往前走，结果就留下两个 1。每个结点最多处理一次，时间 O(n)。
let cur = head
while (cur && cur.next) {
if (cur.val === cur.next.val) cur.next = cur.next.next // 不动 cur
else cur = cur.next
}
// 1->1->2->3->3 变成 1->2->3
原文代码的关键不是 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) {
