怎样合并两个有序链表、删除倒数第 N 个节点？哨兵节点有什么用？

简答

合并两个有序链表，就是把 [1,2,4] 和 [1,3,4] 拼成 [1,1,2,3,4,4]，而且要复用原来的节点。做法像两队人按身高合并成一队：每次比较两队排头，矮的先出列接到结果后面，某一队走完了，就把另一队剩下的整个接上。

删除倒数第 N 个节点，难在单向链表不知道总长度。用两个指针，快指针先走 N 步，然后两个一起走，快指针走到最后一个节点时，慢指针正好停在要删节点的前一个，把它的 next 跳过去就行，只遍历一遍。

两题都会在头节点前放一个不存数据的节点，叫哨兵节点或虚拟头节点。合并时结果链表一开始是空的，删除时要删的可能就是头节点，有了哨兵，这些情况都变成“改某个节点的 next”，不用单独判断。最后返回 dummy.next。

要注意，合并是 O(m + n) 时间、O(1) 额外空间。删除时快指针走 N 步的起点要从哨兵算起，否则删头节点时会差一步；题目保证 N 不超过链表长度，不保证时要先检查快指针有没有走到 null。

两题的写法

先看 mergeTwoLists 里 tail 怎样往后接，再看 removeNthFromEnd 里快指针先走了几步。

JavaScript

function fromArray(values) {
  let head = null;
  for (let i = values.length - 1; i >= 0; i--) head = { val: values[i], next: head };
  return head;
}

function toArray(head) {
  const values = [];
  for (let node = head; node; node = node.next) values.push(node.val);
  return JSON.stringify(values);
}

function mergeTwoLists(a, b) {
  const dummy = { val: 0, next: null };
  let tail = dummy;
  while (a && b) {
    if (a.val <= b.val) {
      tail.next = a;
      a = a.next;
    } else {
      tail.next = b;
      b = b.next;
    }
    tail = tail.next;
  }
  tail.next = a ?? b;
  return dummy.next;
}

function removeNthFromEnd(head, n) {
  const dummy = { val: 0, next: head };
  let fast = dummy;
  let slow = dummy;
  for (let i = 0; i < n; i++) fast = fast.next;
  while (fast.next) {
    fast = fast.next;
    slow = slow.next;
  }
  slow.next = slow.next.next;
  return dummy.next;
}

console.log(toArray(mergeTwoLists(fromArray([1, 2, 4]), fromArray([1, 3, 4])))); // [1,1,2,3,4,4]
console.log(toArray(mergeTwoLists(fromArray([]), fromArray([])))); // []
console.log(toArray(mergeTwoLists(fromArray([]), fromArray([0])))); // [0]

console.log(toArray(removeNthFromEnd(fromArray([1, 2, 3, 4, 5]), 2))); // [1,2,3,5]
console.log(toArray(removeNthFromEnd(fromArray([1]), 1))); // []
console.log(toArray(removeNthFromEnd(fromArray([1, 2]), 1))); // [1]
console.log(toArray(removeNthFromEnd(fromArray([1, 2]), 2))); // [2]

合并时为什么最后一行直接接上剩下的链表？循环结束说明有一条已经走完，另一条剩下的部分本身有序，而且都不小于已经接上的节点，所以整段接过去就行，不用再一个个比较。比较用的是 <=，值相等时先取 a 的节点，两条链表里相等的值保持原来的先后。

删除时快慢指针之间始终隔 N 步。快指针停在最后一个节点（fast.next 为 null）时，慢指针后面正好还有 N 个节点，下一个就是倒数第 N 个。最后一个例子删的是倒数第 2 个，也就是头节点，这时快指针走两步就到了尾部，慢指针还停在哨兵上，dummy.next 改成指向 2。没有哨兵的话，这种情况就得单独写 return head.next。

哨兵节点还能用在哪

凡是“头节点可能变”的链表操作都可以先放一个哨兵：删除所有值等于某个数的节点、分隔链表、在有序链表里插入。代价只是多建一个对象，换来的是不再写 if (!head)、if (要删的是头) 这类分支。

常见追问

合并两个有序链表能用递归写吗？

能。比较两个头，较小的那个的 next 等于“它剩下的部分和另一条链表合并的结果”，任一条为空就返回另一条。代码更短，但递归深度等于两条链表的总长度，链表很长时可能栈溢出，迭代写法只要 O(1) 额外空间。

合并 K 个有序链表怎么做？

把每条链表的头放进最小堆，每次取出最小的接到结果后面，再把它的下一个节点放进堆，时间 O(N log k)，N 是节点总数。最小堆的写法见《前端任务怎样按优先级排队？二叉堆为什么不需要每次完整排序？》。也可以两两合并，像归并排序那样分治。

不用快慢指针，先求长度再删可以吗？

可以。先遍历一遍求出长度 L，再从哨兵走 L − N 步，就停在要删节点的前一个。时间同样 O(L)，只是遍历了两遍，题目的进阶要求是一遍完成，所以面试一般期待快慢指针。