题目描述

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

　　示例:

　　输入:

　　[

　　1->4->5.

　　1->3->4.

　　2->6

　　]

　　输入

　　输出

　　题目解析

　　这里需要将这 k 个排序链表整合成一个排序链表，也就是说有多个输入，一个输出，类似于漏斗一样的概念。

　　因此，可以利用最小堆的概念。如果你对堆的概念不熟悉，可以戳这先了解一下~

　　取每个 Linked List 的最小节点放入一个 heap 中，排序成最小堆。然后取出堆顶最小的元素，放入输出的合并 List 中，然后将该节点在其对应的 List 中的下一个节点插入到 heap 中，循环上面步骤，以此类推直到全部节点都经过 heap。

　　由于 heap 的大小为始终为 k ，而每次插入的复杂度是 logk ，一共插入了 nk 个节点。时间复杂度为 O(nklogk)，空间复杂度为O(k)。

　　代码实现

　　class Solution {

　　public ListNode mergeKLists(ListNode[] lists) {

　　//用heap(堆)这种数据结构，也就是 java 里面的 PriorityQueue

　　PriorityQueue pq = new PriorityQueue<>(new Comparator() {

　　public int compare(ListNode a, ListNode b) {

　　return a.val-b.val;

　　}

　　});

　　ListNode ret = null, cur = null;

　　for(ListNode node: lists) {

　　if(null != node) {

　　pq.add(node);

　　}

　　}

　　while(!pq.isEmpty()) {

　　ListNode node = pq.poll();

　　if(null == ret) {

　　ret = cur = node;

　　}

　　else {

　　cur = cur.next = node;

　　}

　　if(null != node.next) {

　　pq.add(node.next);

　　}

　　}

　　return ret;

　　}

　　}

下一篇

合并两个有序链表