合并两个有序链表 (opens new window)

• 难度：Easy
• 标签：链表 排序

刷题思路

• [x] 迭代推进
• [x] 递归推进

方法 1 迭代推进

• 思路: 迭代推进，一个链表以上为空时停止，将剩余节点尾插到结果
• 复杂度：
  • 时间 O(m+n) 约等于一次遍历（可能提前结束）
  • 空间 O(1) 常量级空间
• 结果：
  • 执行用时：84 ms, 在所有 JavaScript 提交中击败了84.86%的用户
  • 内存消耗：38.8 MB, 在所有 JavaScript 提交中击败了36.52%的用户

var mergeTwoLists = function(l1, l2) {
    const head = new ListNode(null)
    let curr = head
    while (l1 && l2) {
        if (l1.val < l2.val) {
            curr.next = new ListNode(l1.val)
            l1 = l1.next
        } else {
            curr.next = new ListNode(l2.val)
            l2 = l2.next
        }
        curr = curr.next
    }
    curr.next = l1 ? l1 : l2
    return head.next
};

方法 2 递归推进

• 思路: 对比两链表首位，将后续链表和另一链表递归结果尾接到当前节点.
• 复杂度：
  • 时间 O(m+n) 约等于一次遍历（可能提前结束）
  • 空间 O(m+n) 存在递归调用栈消耗，且解题非尾递归故无法省去该消耗，约等于遍历次数.
• 结果:
  • 执行用时：88 ms, 在所有 JavaScript 提交中击败了74.88%的用户
  • 内存消耗：38.8 MB, 在所有 JavaScript 提交中击败了37.98%的用户

var mergeTwoLists = function(l1, l2) {
    if (!l1) return l2
    if (!l2) return l1
    if (l1.val < l2.val) {
        l1.next = mergeTwoLists(l1.next, l2) // 计算未排序部分
        return l1
    } else {
        l2.next = mergeTwoLists(l1, l2.next)
        return l2
    }
};

JS刷题记录 Leetcode-js (opens new window) 每周都会更新刷题心得或者题解, 你的点赞或 star 都将助力我产出更好内容~