题目描述

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

解题思路

递归解法

1
2
3
4
5
6
7
8
9
10
11
12
var mergeTwoLists = function(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;
    }
};

迭代解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
var mergeTwoLists = function(l1, l2) {
    const prehead = new ListNode(-1);
    let prev = prehead;
    
    while (l1 != null && l2 != null) {
        if (l1.val <= l2.val) {
            prev.next = l1;
            l1 = l1.next;
        } else {
            prev.next = l2;
            l2 = l2.next;
        }
        prev = prev.next;
    }
    
    prev.next = l1 === null ? l2 : l1;
    return prehead.next;
};

解题要点

  1. 递归思路

    • 比较两个链表当前节点的值
    • 较小值的节点指向其余节点的合并结果
    • 基线条件是某个链表为空

  2. 迭代思路

    • 创建哑节点作为头部
    • 比较并连接较小的节点
    • 处理剩余节点

复杂度分析

  • 时间复杂度: O(n + m)
  • 空间复杂度:
    • 递归: O(n + m)
    • 迭代: O(1)

参考资料