leetcode题解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 = [[]]
输出：[]

提示：

k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i] 按升序排列
lists[i].length 的总和不超过 10^4

分析

该题的想法应该很简单：利用归并排序的思想，利用k个指针分别指向k个链表的头，然后比较k个指针指向的数的大小，将最小的那个添加到结果链表中，然后将取得最小值的那个链表的指针指向下个结点，接着继续比较k个指针指向的数的大小，重复上述步骤。

该题关键在于是不是每次都需要重新比较k个数的大小，这样比较每次都要o(klogk)的时间复杂度。显然不是，对于一个已经排好序的数列，每次只需要进出一个数，这时可以考虑用最小堆实现的优先队列，该数据结构可以在排好序的数组中插入一个新的数，且时间复杂度降到o(logk)。关于最大堆最小堆的原理可以查看这篇博客java数据结构：基于树的堆。

算法

使用最小堆维护一个优先队列pqueue
遍历所有链表的头指针，并添加到pqueue
初始化结果伪链表头fhead和当前结点curr=fhead，进入循环体，直到pqueue为空
令node=pqueue.pop()，并将node添加到结果链表中curr->next = node，更新curr=curr->next
如果node.next不为空指针，则将node.next添加到pqueue中，回到第4步，并直到循环结束
返回fhead->next

代码

python3

import heapq

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def mergeKLists(self, lists):
        plist = []
        # 由于headq不能自定义比较器，所以需要一个序号i，在结点的val相同时，比较序号来排序
        i = 0
        for node in lists:
            if node is not None:
                heapq.heappush(plist, (node.val, i, node))
                i += 1

        fhead = ListNode()
        curr = fhead
        while len(plist) > 0:
            node = heapq.heappop(plist)[2]
            curr.next = node
            curr = curr.next

            if node.next is not None:
                heapq.heappush(plist, (node.next.val, i, node.next))
                i += 1

        return fhead.next

c++

#include <queue>
using namespace std;

class Solution {
public:
    struct Item {
        ListNode *node;
        bool operator < (const Item &item) const {
            return node->val > item.node->val;
        }
    };
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<Item> plist;
        for (auto node : lists) {
            if (node) plist.push({ node });
        }
        ListNode fhead, *curr = &fhead;
        while (!plist.empty()) {
            auto item = plist.top();
            plist.pop();
            curr->next = item.node;
            curr = curr->next;
            if (item.node->next) plist.push({ item.node->next });
        }
        return fhead.next;
    }
};

java

import java.util.PriorityQueue;

class Solution {
    class Item implements Comparable<Item>{
        ListNode node;

        Item(ListNode node){
            this.node = node;
        }

        public int compareTo(Item item2){
            return this.node.val - item2.node.val;
        }
    }

    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<Item> pqueue = new PriorityQueue<Item>();
        for (ListNode node : lists){
            if(node != null) pqueue.offer(new Item(node));
        }
        ListNode fhead = new ListNode(0);
        ListNode curr = fhead;
        while (!pqueue.isEmpty()){
            Item item = pqueue.poll();
            curr.next = item.node;
            curr = curr.next;

            if(item.node.next != null) pqueue.offer(new Item(item.node.next));
        }
        return fhead.next;
    }
}