算法leetcode

力扣23-合并K个升序链表

字数统计: 1.2k字   |   阅读时长: 5分
,

今天我们继续看一道经典题(陈题)，leetcode第23题，合并 K 个升序链表。

本题有两个主流解法：

算法1：堆
算法2：分治

这两个都是在 leetcode 上能整理出几十道题的常见算法，并且有一定难度，周赛的 B 和 C 题中经常会出现。

很多链表的操作会以本题为组件，例如链表的归并排序，例如 leetcode 第 355 题，设计推特，等等。

下面我们看一下这个题

$1 题目

题目链接

23. 合并K个升序链表

题目描述

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

样例

示例 1：
输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

示例 2：
输入：lists = []
输出：[]

示例 3：
输入：lists = [[]]
输出：[]

$2 题解

算法1: 堆

维护容量为 k 的最小堆，里面始终维护当前的最多 k 个链表的最小元素的排序，堆顶为这 k 个链表最小元素中的最小的，归并后链表的下一个元素即为堆顶元素，将堆头出堆，并将堆头对应的链表节点的下一节点进堆，如果没有下一节点则跳过。

将所有元素均访问一遍后，按照出堆顺序组织的新链表就是归并后的链表。

时间复杂度 $O(N\log K)$

代码

  • 自定义比较的方法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
36
37
38
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.empty()) return nullptr;
        priority_queue<ListNode*, vector<ListNode*>, Cmp> pq;
        for(ListNode *iter : lists)
        {
            if(iter != nullptr)
                pq.push(iter);
        }
        if(pq.empty()) return  nullptr;
        ListNode *top = pq.top();
        pq.pop();
        ListNode *result = top;
        if(top -> next != nullptr)
            pq.push(top -> next);
        ListNode *tail = result;
        while(!pq.empty())
        {
            ListNode *top = pq.top();
            pq.pop();
            tail -> next = top;
            if(top -> next != nullptr)
                pq.push(top -> next);
            tail = tail -> next;
        }
        return result;
    }

private:
    struct Cmp
    {
        bool operator () (ListNode *left, ListNode *right)
        {
            return (left -> val) > (right -> val); // > 是小顶堆；< 是大顶堆
        }
    };
};
  • 自定义比较的方法法二
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
bool operator <(const ListNode &left, const ListNode &right)
{
    // 形参必须写引用
    return (left.val) > (right.val);
}

class Solution_2 {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.empty()) return nullptr;
        priority_queue<ListNode> pq;
        for(ListNode *iter : lists)
        {
            if(iter != nullptr)
                pq.push(*iter);
        }
        if(pq.empty()) return  nullptr;
        ListNode top = pq.top();
        pq.pop();
        if(top.next != nullptr)
            pq.push(*(top.next));
        ListNode *result = new ListNode(top.val);
        ListNode *tail = result; // 迭代的时候还是用指针
        while(!pq.empty())
        {
            ListNode top = pq.top();
            pq.pop();
            if(top.next != nullptr)
                pq.push(*(top.next));
            tail -> next = new ListNode(top.val);
            tail = tail -> next;
        }
        return result;
    }
};

算法2: 分治

目标是归并 K 个链表，用分治的思维模式

  • 分解：将 K 个链表分为两份，每份 K / 2 个链表
  • 解决：如果 K = 1，可以直接解决，将链表直接返回即可
  • 合并：将两个有序链表归并成一个

时间复杂度：$O(N\log N)$

代码: 自顶向下

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
36
37
38
39
40
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.empty()) return nullptr;
        int n = lists.size();
        ListNode *result = _mergeKLists(lists, 0, n - 1);
        return result;
    }

private:
    ListNode* _mergeKLists(vector<ListNode*>& lists, int left, int right)
    {
        if(left == right)
            return lists[left];
        if(left + 1 == right)
            return _mergeTwoLists(lists[left], lists[right]);
        int mid = left + (right - left) / 2;
        ListNode *left_merged = _mergeKLists(lists, left, mid - 1);
        ListNode *right_merged = _mergeKLists(lists, mid, right);
        return _mergeTwoLists(left_merged, right_merged);
    }

    ListNode* _mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode *result = new ListNode(-1);
        ListNode *cur = result;
        while (l1 && l2) {
            if(l1 -> val < l2 -> val) {
                cur -> next = l1;
                l1 = l1 -> next;
            } else {
                cur -> next = l2;
                l2 = l2 -> next;
            }
            cur = cur -> next;
        }
        if(l1) cur->next = l1;
        if(l2) cur->next = l2;
        return result -> next;
    }
};

代码：自底向上

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
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.empty()) return nullptr;
        int n = lists.size();
        while (n > 1)
        {
            // n 每轮减小一半
            int k = (n + 1) / 2;
            for(int i = 0; i < n / 2; ++i)
                lists[i] = _mergeTwoLists(lists[i], lists[i + k]);
            n = k;
        }
        return lists[0];
    }

private:
    ListNode* _mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode *result = new ListNode(-1);
        ListNode *cur = result;
        while (l1 && l2) {
            if(l1 -> val < l2 -> val) {
                cur -> next = l1;
                l1 = l1 -> next;
            } else {
                cur -> next = l2;
                l2 = l2 -> next;
            }
            cur = cur -> next;
        }
        if(l1) cur->next = l1;
        if(l2) cur->next = l2;
        return result -> next;
    }
};
Share