手帐 Blog

主题

复盘 · LC 21 合并两个有序链表 ​

题目 ​

题意 ​

给定两条非递减有序单链表 list1、list2，把它们合并成一条仍有序的新链表（可复用原节点），返回新链表头。

边界：一条为空、两条都空、长度差很大、有重复值。

涉及算法 ​

标签一句话
双指针 / 归并谁小接谁，接完把剩余尾巴挂上
哨兵节点dummy 省掉「第一个节点特判」

教程对照：13 · 链表进阶（环检测、相交、合并两有序链表）。

评价我的解法 ​

我的代码（摘自 21-合并两个有序链表/index.js，不含本地测例）：

javascript
var mergeTwoLists = function (list1, list2) {
  if (list1 === null && list2 === null) {
    return null;
  }
  const nodeList = [];
  while (true) {
    if (!list1) {
      break;
    }
    nodeList.push(list1);
    list1 = list1.next;
  }
  while (true) {
    if (!list2) {
      break;
    }
    nodeList.push(list2);
    list2 = list2.next;
  }
  const resNodeList = nodeList.sort((a, b) => {
    return a.val - b.val;
  });
  for (let i = 0; i < resNodeList.length - 1; i++) {
    const curNode = resNodeList[i];
    const nextNode = resNodeList[i + 1];
    curNode.next = null;
    nextNode.next = null;
    curNode.next = nextNode;
  }
  return resNodeList[0];
};

能 AC：两链拆进数组 → 按 val 排序 → 再接线，结果正确；双空提前返回也合理。

  • 时间 O((m+n) log(m+n))，空间 O(m+n)（数组）。
  • 糙点：题目已保证有序，排序等于把「归并」退化成「全局重排」；while (true) + 先断链再接线偏绕；双空特判可省略（空数组时 resNodeList[0] 本就是 undefined/null 语义，更干净是直接走归并）。
  • 和 7/21 的 206/234 同一习惯：先数组再处理——能过，但不是链表题面试想听的模板。

最佳题解 ​

双指针归并 + 哨兵（O(m+n) 时间、O(1) 额外空间）：

javascript
/**
 * @param {ListNode} list1
 * @param {ListNode} list2
 * @return {ListNode}
 */
var mergeTwoLists = function (list1, list2) {
  const dummy = new ListNode(0);
  let cur = dummy;
  while (list1 && list2) {
    if (list1.val <= list2.val) {
      cur.next = list1;
      list1 = list1.next;
    } else {
      cur.next = list2;
      list2 = list2.next;
    }
    cur = cur.next;
  }
  cur.next = list1 || list2;
  return dummy.next;
};
  • 时间 O(m+n)，空间 O(1)（不计输出链本身）。
  • 为何更优：利用有序性一次扫完；哨兵让「接节点」全程同构。

关联题目 ​

题为何相关
88. 合并两个有序数组同一归并思想，落到数组
23. 合并 K 个升序链表21 的多路扩展
148. 排序链表归并排序在链表上的完整版

一句话带走 ​

合并两有序链表：别先拆进数组再 sort——谁小接谁，尾巴挂上，哨兵省特判。