题目描述

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

样例

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

算法分析

• 1、一开始先用小根堆存储k个排序链表的头指针，每次操作后用小根堆维护k个链表当前元素最小的指针，并以指针对应的值进行排序
• 2、操作过程中，当小根堆不为空时，堆顶元素即当前k个排序链表当前最小的元素的指针t，将该值加入到dummy链表的后面，并把t指针往后走一位，使得t指针指向的值变大，再加入到小根堆中

时间复杂度 $O(nlogk)$

n表示的是所有链表的总长度，k表示k个排序链表

Java 代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> q = new PriorityQueue<ListNode>((x,y) -> (x.val - y.val));
        for(int i = 0;i < lists.length;i ++) if(lists[i] != null) q.add(lists[i]);

        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;

        while(!q.isEmpty())
        {
            ListNode t = q.poll();
            cur.next = new ListNode(t.val);
            //更新cur
            cur = cur.next;
            //将下一个位置放进堆中
            t = t.next;
            if(t != null) q.add(t);
        }
        return dummy.next;
    }
}