Vault 101

xjay2007's Blog

0%

LeetCode 23. 合并k个排序链表

发表于 更新于 分类于 ， Valine：

题目描述

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

1
2
3
4
5
6
7
输入:
[
  1->4->5,
  1->3->4,
  2->6
]
输出: 1->1->2->3->4->4->5->6

题解

暴力法

  • 遍历所有链表，将所有数字放入数组
  • 对数组进行排序
  • 根据排序后的数组生成新链表

复杂度分析

  • 时间复杂度： O(N log N) ，N 为所有的节点数.
    • 遍历所有节点耗时 O(N) .
    • 对数组排序耗时 O(N log N).
    • 遍历数组并创建新链表耗时 O(N) .
  • 空间复杂度： O(N).
    • 对数组排序 O(N) ,（根据选择的排序算法）.
    • 创建新链表 O(N) .

依次比较

算法

  • 依次比较 k 个链表的头节点，找出最小值.
  • 如找到头节点，将此头节点指向它的下个 节点.

复杂度

  • 时间复杂度： O(kN) ，k 为链表数.
    • 每次比较需要耗费 O(k) , 需要做 k-1 次比较.

优先队列

算法

  • 与依次比较相同，比较过程中使用优先队列来做优化.

复杂度

  • 时间复杂度：O(N log k) ，k 为链表数.
    • 使用优先队列，pop 和 push 操作时间复杂度可以降低到 O(log k) . 找出最小数值节点时间复杂度 O(1).
  • 空间复杂度
    • 创建一个新节点 O(n)
    • 使用原地拼接链表 O(1). 优先队列(在堆上实现)需要 O(k).

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// C++
ListNode* mergeKListsPriorityQueue(vector<ListNode*>& lists) {
    ListNode dummyRoot(0);
    auto p = &dummyRoot;
    auto cmp = [](ListNode* l1, ListNode* l2) {
        return l1->val > l2->val;
    };
    priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> queue(cmp);
    for (auto i = 0; i < lists.size(); ++i) {
        auto l = lists[i];
        if (l) {
            queue.push(l);
        }
    }
    while (!queue.empty()) {
        auto top = queue.top();
        queue.pop();
        p->next = top;
        p = p->next;
        if (top->next) {
            queue.push(top->next);
        }
    }
    return dummyRoot.next;
}

分治法

算法

  • 将合并 k 条链表分解为合并 2 条链表.

    • 将 k 进行两两合并.
    • 第一次合并后，还有 k/2 条，平均每条长度 2N/k, 然后继续两两合并，下次合并还有 k/4, k/8 …
    • 直到合并完最后两条.
    • 需要 log~2~ k次合并.

    参考图

复杂度

  • 时间复杂度： O(N log k)
    • 合并两条链表 O(n).
    • 需要比较 O(log k) 次.
  • 空间复杂度：O(1)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// C++
// 合并两个链表
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    ListNode dummyRoot(0);
    auto p = &dummyRoot;
    while (l1 && l2) {
        if (l1->val < l2->val) {
            p->next = l1;
            l1 = l1->next;
        } else {
            p->next = l2;
            l2 = l2->next;
        }
        p = p->next;
    }
    p->next = l1 ? l1 : l2;
    return dummyRoot.next;
}
// 合并k个链表
ListNode* mergeKListsDivide(vector<ListNode*>& lists) {
    ListNode dummyRoot(0);
    auto p = &dummyRoot;
    auto step = 1;
    auto size = lists.size();
    while (step < size) {
        for (auto i = 0; i < size - step; i += step * 2) {
            lists[i] = mergeTwoLists(lists[i], lists[i+step]);
        }
        step *= 2;
    }
    if (size > 0) {
        p->next = lists[0];
    }
    return dummyRoot.next;
}

参考链接

相似文章