23. 合并K个升序链表

23. 合并K个升序链表

• 解题思路
• 代码

解题思路

其实最开始的思路是N个指针，每次放最小的进新链表，但是这样时间复杂度太高了！合并两个有序链表可以考虑这样做。所以我选择维护一个小顶堆，将所有的元素都加入小顶堆，然后再出来的时候就是按照升序的顺序了。

对应到代码的话，相当于我们需要准备一个「集合」，将所有链表的头结点放入「集合」，然后每次都从「集合」中挑出最小值，并将最小值的下一个节点添加进「集合」（如果有的话），循环这个过程，直到「集合」为空（说明所有节点都处理完，进过集合又从集合中出来）。
注意题目是有序链表，所以我们一开始只需要放入头节点来比较

代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length==0) return null;//空链表直接返回
        PriorityQueue<ListNode> sHeap = new PriorityQueue<ListNode>((a, b) -> a.val - b.val);
               
        ListNode fake = new ListNode();
        ListNode cur = fake;//保留头结点作为信标
        for(ListNode node:lists){
            if(node!=null){
                sHeap.add(node);//加入最小堆
            }
        }
        while(!sHeap.isEmpty()){
            ListNode poll = sHeap.poll();
            cur.next = poll;
            cur=cur.next;

            // 将最小值的下一个节点添加进「集合」（如果有的话）
            if(poll.next!=null){

                sHeap.add(poll.next);//头节点放了，如果头节点还有下一个那就把下一个要放进小顶堆
            }
        }
        return fake.next;
    }
}