跳到主要内容

合并两个有序链表

问题​

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

输入：l1 = [], l2 = []
输出：[]

输入：l1 = [], l2 = [0]
输出：[0]

来源：LeetCode 21. 合并两个有序链表

前置知识：链表节点定义​

ListNode.ts
class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val: number = 0, next: ListNode | null = null) {
    this.val = val;
    this.next = next;
  }
}
什么是链表？

链表是一种线性数据结构，每个节点包含数据和指向下一个节点的指针。与数组不同，链表的元素在内存中不是连续存储的，插入/删除效率高但随机访问效率低。

答案​

方法一：迭代（推荐）​

核心思路：创建一个虚拟头节点（dummy），用指针逐步比较两个链表的节点值，将较小的接到结果链表后面。

mergeTwoListsIterative.ts
function mergeTwoLists(
  list1: ListNode | null,
  list2: ListNode | null
): ListNode | null {
  // 虚拟头节点，简化边界处理
  const dummy = new ListNode(-1);
  let current = dummy;

  // 两个链表都不为空时，逐个比较
  while (list1 !== null && list2 !== null) {
    if (list1.val <= list2.val) {
      current.next = list1;
      list1 = list1.next;
    } else {
      current.next = list2;
      list2 = list2.next;
    }
    current = current.next;
  }

  // 将剩余部分接上（只会有一个链表有剩余）
  current.next = list1 ?? list2;

  return dummy.next;
}

执行过程演示：

l1: 1 → 2 → 4
l2: 1 → 3 → 4

dummy → 

Step 1: l1.val(1) <= l2.val(1) → 接 l1(1)
  dummy → 1 →        l1 移到 2，l2 还在 1

Step 2: l1.val(2) > l2.val(1) → 接 l2(1)
  dummy → 1 → 1 →    l1 还在 2，l2 移到 3

Step 3: l1.val(2) < l2.val(3) → 接 l1(2)
  dummy → 1 → 1 → 2 →    l1 移到 4，l2 还在 3

Step 4: l1.val(4) > l2.val(3) → 接 l2(3)
  dummy → 1 → 1 → 2 → 3 →    l1 还在 4，l2 移到 4

Step 5: l1.val(4) <= l2.val(4) → 接 l1(4)
  dummy → 1 → 1 → 2 → 3 → 4 →    l1 为 null，l2 还在 4

循环结束，l1 为 null，接上 l2 剩余：
  dummy → 1 → 1 → 2 → 3 → 4 → 4

返回 dummy.next
复杂度分析
  • 时间复杂度：O(m+n)O(m + n) — m、n 分别是两个链表的长度
  • 空间复杂度：O(1)O(1) — 只使用常数额外空间（不算输出）
dummy 节点技巧

虚拟头节点（哨兵节点）是链表题的常用技巧，可以避免处理"头节点为空"的特殊情况，简化代码逻辑。

方法二：递归​

核心思路：递归地比较两个链表的头节点，较小的节点的 next 指向剩余部分的合并结果。

mergeTwoListsRecursive.ts
function mergeTwoLists(
  list1: ListNode | null,
  list2: ListNode | null
): ListNode | null {
  // 递归终止条件：某个链表为空
  if (list1 === null) return list2;
  if (list2 === null) return list1;

  if (list1.val <= list2.val) {
    // list1 较小，它的 next 指向剩余部分的合并结果
    list1.next = mergeTwoLists(list1.next, list2);
    return list1;
  } else {
    list2.next = mergeTwoLists(list1, list2.next);
    return list2;
  }
}

递归展开：

merge([1,2,4], [1,3,4])
= 1 → merge([2,4], [1,3,4])        // l1.val(1) <= l2.val(1)，取 l1
= 1 → 1 → merge([2,4], [3,4])      // l1.val(2) > l2.val(1)，取 l2
= 1 → 1 → 2 → merge([4], [3,4])    // l1.val(2) < l2.val(3)，取 l1
= 1 → 1 → 2 → 3 → merge([4], [4])  // l1.val(4) > l2.val(3)，取 l2
= 1 → 1 → 2 → 3 → 4 → merge([], [4]) // l1.val(4) <= l2.val(4)，取 l1
= 1 → 1 → 2 → 3 → 4 → 4           // l1 为 null，返回 l2
复杂度分析
  • 时间复杂度：O(m+n)O(m + n)
  • 空间复杂度：O(m+n)O(m + n) — 递归调用栈的深度

递归方法虽然优雅，但会占用额外的栈空间，链表很长时可能导致栈溢出。面试中建议先写迭代法，再提递归法作为补充。

方法三：转数组排序再构建链表（不推荐）​

先把两个链表的值提取到数组，排序后重新构建链表：

mergeTwoListsArray.ts
function mergeTwoLists(
  list1: ListNode | null,
  list2: ListNode | null
): ListNode | null {
  const values: number[] = [];

  // 收集所有值
  let p = list1;
  while (p) { values.push(p.val); p = p.next; }
  p = list2;
  while (p) { values.push(p.val); p = p.next; }

  // 排序
  values.sort((a, b) => a - b);

  // 构建新链表
  const dummy = new ListNode(-1);
  let current = dummy;
  for (const val of values) {
    current.next = new ListNode(val);
    current = current.next;
  }

  return dummy.next;
}
不推荐
  • 时间复杂度：O((m+n)log⁡(m+n))O((m+n)\log(m+n)) — 因为额外排序
  • 空间复杂度：O(m+n)O(m + n) — 额外数组
  • 没有利用已排序的特性，效率较低

常见面试追问​

Q1: 如何合并 K 个有序链表？​

答案：这是 LeetCode 23，有三种经典方法：

// 方法：分治合并（最优）
function mergeKLists(lists: (ListNode | null)[]): ListNode | null {
  if (lists.length === 0) return null;
  if (lists.length === 1) return lists[0];

  const mid = Math.floor(lists.length / 2);
  const left = mergeKLists(lists.slice(0, mid));
  const right = mergeKLists(lists.slice(mid));

  return mergeTwoLists(left, right);
}
// 时间复杂度：O(N log k)，N 是所有节点总数，k 是链表数量

Q2: dummy 节点有什么作用？能不能不用？​

答案：可以不用，但代码会更复杂，需要单独处理头节点：

function mergeTwoListsNoDummy(
  list1: ListNode | null,
  list2: ListNode | null
): ListNode | null {
  if (!list1) return list2;
  if (!list2) return list1;

  let head: ListNode;
  if (list1.val <= list2.val) {
    head = list1;
    list1 = list1.next;
  } else {
    head = list2;
    list2 = list2.next;
  }

  let current = head;
  while (list1 && list2) {
    if (list1.val <= list2.val) {
      current.next = list1;
      list1 = list1.next;
    } else {
      current.next = list2;
      list2 = list2.next;
    }
    current = current.next;
  }
  current.next = list1 ?? list2;

  return head;
}

Q3: 这题有什么实际应用？​

答案：

  • 归并排序：核心步骤就是合并两个有序序列
  • 数据库查询：合并两个有序的查询结果集（Merge Join）
  • 日志合并：多个日志文件按时间戳合并

相关链接​