合并两个有序链表

题目描述

给你两个升序链表的头节点 list1 和 list2，请你将两个链表合并为一个升序链表。

新链表是通过拼接给定的两个链表的所有节点组成的，返回合并后链表的头节点。

示例

输入：list1 = [1,2,4], list2 = [1,3,4]
输出：[1,1,2,3,4,4]

输入：list1 = [], list2 = []
输出：[]

输入：list1 = [], list2 = [0]
输出：[0]

约束条件

• 两个链表的节点数目范围是 [0, 50]
• -100 <= Node.val <= 100
• list1 和 list2 均按非递减顺序排列

我的解题过程

第一次尝试：递归思路（但实现不够优雅）

最开始想到的是用递归来解决。思路是：依次比较两个链表当前节点的值，把较小的节点连接到结果链表上，然后递归处理剩余节点。

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode | null {
  let head = new ListNode(0);

  const getNode = (l1, l2, h) => {
    let cur = h;

    if (l1 === null) {
      cur.next = l2;
      return;
    }
    if (l2 === null) {
      cur.next = l1;
      return;
    }
    const v1 = l1.val;
    const v2 = l2.val;
    if (v1 < v2) {
      cur.next = l1;
      l1 = l1.next;
      cur = cur.next;
      getNode(l1, l2, cur);
    } else {
      cur.next = l2;
      l2 = l2.next;
      cur = cur.next;
      getNode(l1, l2, cur);
    }
  };

  getNode(list1, list2, head);

  return head.next;
}

这个版本虽然能工作，但有几个问题：

• 通过传递引用来修改节点，不太符合递归的思想
• 递归函数没有返回值，逻辑不够清晰
• 代码比较冗长，有很多重复的逻辑

第二次尝试：迭代（双指针）

后来发现其实可以用更简单直观的迭代方式来解决。既然两个链表都是有序的，那就用双指针同时遍历，每次选择较小的节点加到结果链表中。

关键思路：

1. 创建一个虚拟头节点（dummy），简化边界处理
2. 用一个指针 current 来构建新链表
3. 同时遍历两个链表，比较节点值，将较小的接到 current 后面
4. 最后处理剩余的节点（总有一个链表会先遍历完）

function mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode | null {
  const dummy = new ListNode(0); // 虚拟头节点
  let current = dummy;

  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 dummy.next;
}

这个版本简洁明了，思路很清晰：

• 虚拟头节点：避免了处理第一个节点的特殊情况
• 循环条件：while (list1 && list2) 确保两个链表都还有节点
• 剩余处理：循环结束后，用 list1 || list2 一行代码就能处理剩余节点

时间复杂度 O(m+n)，空间复杂度 O(1)（只使用了几个指针）。

进阶思考：更优雅的递归实现

虽然迭代方式已经很好了，但递归其实也可以写得很优雅。关键在于：递归函数应该返回合并后的链表头节点，而不是通过传递引用来修改。

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 = mergeTwoLists(list1.next, list2);
    return list1;
  } else {
    list2.next = mergeTwoLists(list1, list2.next);
    return list2;
  }
}

这个递归版本非常简洁优雅：

• 终止条件：如果某个链表为空，直接返回另一个链表
• 递归逻辑：比较两个节点值，选择较小的，将其 next 指向递归处理剩余部分的结果
• 返回值：返回较小的那个节点作为当前段的头节点

这种写法更符合函数式编程思想，每次递归都返回一个新的链表头，逻辑清晰且代码简洁。