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

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

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

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

链表的合并

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