23. 合并K个升序链表

我就是我 2023-10-04 08:29 24阅读 0赞

#### 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;
        }
    }