链表结构相对数组、字符串来说，稍微有那么一些些复杂，所以针对链表的真题戏份也相对比较多。 前面咱们说过，数组、字符串若想往难了出，那一定是要结合一些超越数据结构本身的东西——比如排序算法、二分思想、动态规划思想等等。因此，这部分对应的难题、综合题，我们需要等知识体系完全构建起来之后，在真题训练环节重新复盘。

但是链表可不一样了。如果说在命题时，数组和字符串的角色往往是“算法思想的载体”，那么链表本身就可以被认为是“命题的目的”。单在真题归纳解读环节，我们能讲的技巧、能做的题目已经有很多。结合实际面试中的命题规律，我把这些题目分为以下三类：

• 链表的处理：合并、删除等（删除操作画个记号，重点中的重点！）
• 链表的反转及其衍生题目
• 链表成环问题及其衍生题目

本节我们就以链表的处理为切入点，一步一步走进链表的世界。

链表的合并

⚡ 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 分别指向未处理部分最小值。每轮至少推进一个指针，必然终止。该版本会重连原结点；如果其他调用方仍持有旧链并假设其结构不变，应复制结点或明确转移所有权。

真题描述：将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有结点组成的。