# 合并K个升序链表 (opens new window)

  • 难度：Hard
  • 标签：链表 排序 二分法 递归 优先级队列 小顶堆
  • Tip:
  • 设定: 输入数组长度为 k, 每个元素长度为 n.

# 刷题思路

  • [x] 两两合并 O(k^2 * n)
  • [x] 二分法递归 O(klogk * n)
  • [ ] 优先级队列 O(klogk * n)
  • [ ] 暴力K指针
  • [ ] 小顶堆

# 方法 1 两两合并

  • 思路: 遍历入参, 两两合并（每轮都生成新的链表）
  • 复杂度：
    • 时间 O(k^2 *N) 计算次数渐进趋势为 2n+3n+4n+...+k*n, 即 k^2 * n
    • 空间 O(1)
  • 结果:
    • 执行用时：356 ms, 在所有 JavaScript 提交中击败了22.60%的用户
    • 内存消耗：45.5 MB, 在所有 JavaScript 提交中击败了7.72%的用户
var mergeKLists = function(lists) {
    if (lists.length === 0) return null
    if (lists.length === 1) return lists[0]
    return lists.reduce((a, b) => mergeTwoLists(a, b))
};

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(klogk * N) 对入参数组进行二分，复杂度为O(klogk)，乘上复杂度为 O(N) 的合并函数.
    • 空间 O(logk) 存在递归调用栈, 由于是对入参数组进行二分递归，故计算为 O(logk).
  • 结果:
    • 执行用时：96 ms, 在所有 JavaScript 提交中击败了97.27%的用户
    • 内存消耗：44.4 MB, 在所有 JavaScript 提交中击败了17.46%的用户
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
var mergeKLists = function(lists) {
    const len = lists.length
    if (len === 0) return null
    return recursion(lists, 0, lists.length-1)
};

function recursion (lists, start, end) {
    if (end === start) return lists[start]
    const mid = Math.floor((start + end) / 2)
    return mergeTwoLists(recursion(lists, start, mid), recursion(lists, mid+1, end))
}

function mergeTwoLists (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
};

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