LeetCode 23 合并K个排序链表(堆)

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

示例:

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

思路

题意很清楚，现在的问题就是应该怎么合并。

由于每一个链表都是递增的，所以我们维护这三个链表中的三个头节点，每次取出值最小放在最终的答案链表中，这个过程可以使用优先队列来维护，时间复杂度$O(kn*logk)$,空间复杂度为$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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution
{
public:
    struct status
    {
        ListNode *ptr;
        int val;
        bool operator<(const status &rhs) const
        {
            return val > rhs.val;
        }
    };
    ListNode *mergeKLists(vector<ListNode *> &lists)
    {
        ListNode *head = NULL, *last;
        priority_queue<status> q;
        for (ListNode *&node : lists)
            if (node)
                q.push({node, node->val});
        while (!q.empty())
        {
            status cur = q.top();
            q.pop();
            if (head == NULL)
            {
                head = cur.ptr;
                last = head;
            }
            else
            {
                last->next = cur.ptr;
                last = last->next;
            }
            if (cur.ptr->next)
                q.push({cur.ptr->next, cur.ptr->next->val});
        }
        return head;
    }
};

附上之前写的一个手工模拟代码：

 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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class Solution
{
public:
    ListNode *mergeKLists(vector<ListNode *> &lists)
    {
        ListNode *head = NULL;
        while (1)
        {
            int cnt = 0;
            for (ListNode *&node : lists)
            {
                if (node == NULL)
                    cnt++;
                else
                {
                    if (head == NULL)
                    {
                        head = new ListNode(node->val);
                    }
                    else
                    {
                        ListNode *tmpHead = head;
                        if (node->val < head->val)
                        {
                            head = new ListNode(node->val);
                            head->next = tmpHead;
                        }
                        else
                        {
                            while (node->val >= tmpHead->val && tmpHead->next && node->val >= tmpHead->next->val)
                            {
                                tmpHead = tmpHead->next;
                            }
                            if (tmpHead->next)
                            {
                                ListNode *tmp = tmpHead->next;
                                tmpHead->next = new ListNode(node->val);
                                tmpHead->next->next = tmp;
                            }
                            else
                            {
                                tmpHead->next = new ListNode(node->val);
                            }
                        }
                    }
                    node = node->next;
                }
            }
            if (cnt == lists.size())
                break;
        }
        return head;
    }
};

最后修改于 2020-04-26

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。