合并两个有序链表

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

示例 1：

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

输入：l1 = [], l2 = [] 输出：[] 示例 3：

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

进阶做法：要合并两个升序链表为一个新的升序链表，可以使用递归或迭代的方法。以下是两种方法的详细实现：

方法一：递归法

核心思路：
比较两个链表的当前节点，选择较小的节点作为合并后的头节点，递归处理剩余节点。

步骤：

终止条件：若其中一个链表为空，直接返回另一个链表。
递归比较：
- 若 list1.val ≤ list2.val，选择 list1 为头节点，递归合并 list1.next 和 list2。
- 否则，选择 list2 为头节点，递归合并 list1 和 list2.next。

代码实现：

function mergeTwoLists(list1, list2) {
    if (!list1) return list2;
    if (!list2) return list1;
    
    if (list1.val <= list2.val) {
        list1.next = mergeTwoLists(list1.next, list2);
        return list1;
    } else {
        list2.next = mergeTwoLists(list1, list2.next);
        return list2;
    }
}

复杂度分析：

时间复杂度：O(m + n)，其中 m 和 n 分别为两个链表的长度。
空间复杂度：O(m + n)，递归栈深度最大为链表长度之和。

方法二：迭代法（推荐）

核心思路：
使用虚拟头节点（dummy node）和指针遍历，逐个比较两链表节点，按升序连接。

步骤：

创建虚拟头节点：用于简化边界处理。
遍历两链表：
- 比较当前节点，将较小节点连接到结果链表。
- 移动指针继续比较，直到其中一个链表遍历完毕。
连接剩余节点：将另一个链表的剩余部分直接连接到结果链表末尾。

代码实现：

function mergeTwoLists(list1, list2) {
    const dummy = new ListNode(-1); // 虚拟头节点
    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; // 返回虚拟头节点的下一个节点（真正的头节点）
}

复杂度分析：

时间复杂度：O(m + n)，需遍历两链表各一次。
空间复杂度：O(1)，仅需常数级额外空间。

示例验证

输入链表：

list1: 1 → 2 → 4
list2: 1 → 3 → 4

迭代法过程：

初始化：dummy = -1，current = -1。
比较节点：
- 1 ≤ 1 → 连接 list1 的 1，current → 1，list1 → 2。
- 2 > 1 → 连接 list2 的 1，current → 1 → 1，list2 → 3。
- 2 ≤ 3 → 连接 list1 的 2，current → 1 → 1 → 2，list1 → 4。
- 4 ≤ 3 → 连接 list2 的 3，current → 1 → 1 → 2 → 3，list2 → 4。
- 4 ≤ 4 → 连接 list1 的 4，current → 1 → 1 → 2 → 3 → 4，list1 → null。
连接剩余节点：list2 剩余 4，连接后结果为 1 → 1 → 2 → 3 → 4 → 4。

总结

递归法：代码简洁，但可能导致栈溢出，适用于链表较短的场景。
迭代法：空间效率更高，推荐使用。

方法一：递归法​

方法二：迭代法（推荐）​

示例验证​

总结​

方法一：递归法

方法二：迭代法（推荐）

示例验证

总结