JavaScript实现合并两个有序链表：迭代法与递归法详解

合并两个有序链表是算法中的一个经典问题。我们可以通过迭代或递归的方式来实现。以下是使用 JavaScript 实现的两种方法：

1. 迭代法

function mergeTwoLists(l1, l2) {
    // 创建一个虚拟头节点，简化边界条件处理
    const dummy = new ListNode(-1);
    let current = dummy;

    // 遍历两个链表
    while (l1 !== null && l2 !== null) {
        if (l1.val <= l2.val) {
            current.next = l1;
            l1 = l1.next;
        } else {
            current.next = l2;
            l2 = l2.next;
        }
        current = current.next;
    }

    // 如果其中一个链表还有剩余节点，直接连接到结果链表
    if (l1 !== null) {
        current.next = l1;
    } else {
        current.next = l2;
    }

    // 返回合并后的链表头节点
    return dummy.next;
}

2. 递归法

function mergeTwoLists(l1, l2) {
    // 递归终止条件
    if (l1 === null) {
        return l2;
    }
    if (l2 === null) {
        return l1;
    }

    // 比较两个链表的头节点，选择较小的节点作为当前节点
    if (l1.val < l2.val) {
        l1.next = mergeTwoLists(l1.next, l2);
        return l1;
    } else {
        l2.next = mergeTwoLists(l1, l2.next);
        return l2;
    }
}

解释

• 迭代法：我们使用一个虚拟头节点 dummy 来简化边界条件的处理。通过遍历两个链表，每次选择较小的节点连接到结果链表中，直到其中一个链表遍历完毕。最后将剩余的链表直接连接到结果链表的末尾。

• 递归法：递归的核心思想是每次比较两个链表的头节点，选择较小的节点作为当前节点，然后递归地处理剩下的部分。递归终止条件是其中一个链表为空时，直接返回另一个链表。

复杂度分析

• 时间复杂度：O(n + m)，其中 n 和 m 分别是两个链表的长度。因为每次递归或迭代都会处理一个节点，直到所有节点都被处理完毕。
• 空间复杂度：
  • 迭代法：O(1)，只使用了常数级别的额外空间。
  • 递归法：O(n + m)，递归调用栈的深度最多为 n + m。

这两种方法都是有效的，选择哪种方法取决于具体的应用场景和个人偏好。