前端新一水算法系列：每日一题Day2：合并两个有序链表

题目描述

给你两个 升序排列 的链表 l1 和 l2，请你将它们 合并为一个新的升序链表。

新链表由这两个链表的所有节点组成，不需要创建额外数组，只需要通过“指针指来指去”完成合并。

示例：

输入：

l1 = [1,2,4]
l2 = [1,3,4]

输出：

[1,1,2,3,4,4]

提示

如果没有思路，可以参考下面几个方向：

1. 两个链表都是 升序 的，这是关键线索。
2. 就像两条已经排好序的队伍，你每次只需要比较队头，看哪个更小，把它接到新队伍后面。
3. 你不需要一次性全部比较，只需要每次处理最前面的节点。
4. 链表天然从头开始遍历，因此“指针前进”就是全部逻辑。

解题思路（详细、循序渐进、适合零基础）

Step 1：创建虚拟头节点 dummy

为了方便操作链表，我们通常创建一个 dummy（虚拟头），

dummy 的 next 指向我们真正的第一个节点，

这样返回结果时只需要返回 dummy.next。

Step 2：准备 cur 指针

cur 用来构建新的链表，它始终指向新链表的末尾。

Step 3：同时遍历 l1 和 l2

每次比较：

• 如果 l1.val 更小 → 把 l1 接到 cur 后面，l1 前进
• 否则 → 把 l2 接到 cur 后面，l2 前进

然后 cur 指针也往后移动。

Step 4：处理剩余节点

当其中一个链表走完后，另一个链表可能还有剩余节点

（因为两个链表不一定一样长）

剩余的那一条链表本身就已经有序，直接挂到 cur 后面即可。

Step 5：返回结果

最终返回 dummy.next

示例代码（JavaScript，清晰注释）

var mergeTwoLists = function(l1, l2) {
  // 创建虚拟头节点
  let dummy = new ListNode(0);
  let cur = dummy;

  // 当两个链表都没走完时，每次取最小值
  while (l1 !== null && l2 !== null) {
    if (l1.val < l2.val) {
      cur.next = l1;  // l1 更小 → 挂到 cur 后面
      l1 = l1.next;   // l1 前进
    } else {
      cur.next = l2;  // l2 更小
      l2 = l2.next;   // l2 前进
    }
    cur = cur.next;   // 新链表往后延长
  }

  // 把剩余的链表挂到末尾
  if (l1 !== null) {
    cur.next = l1;
  }
  if (l2 !== null) {
    cur.next = l2;
  }

  return dummy.next;
};

复杂度分析

时间复杂度：O(n + m)

空间复杂度：O(1)

因为我们没有创建新的链表节点，只是移动指针，属于原地合并。

前端新一水版权所有，侵权必究！