23. Merge k Sorted Lists #

题目 #

给定一个链表数组，每个链表都已经按升序排列。
将所有链表合并到一个升序链表中，返回合并后的链表。

思路 #

构造大小为 K 的小根堆
建立堆结点和链表结点的映射
堆结点与链表结点共享变量 val
每次在堆中取最小值的结点，根据映射查找到相应链表节点，并加入到已有链表末尾。

代码 #

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 {
    private class HeapNode implements Comparable<HeapNode> {
        public int val;
        public ListNode ptr;
        
        HeapNode(int val, ListNode ptr) {
            this.val = val;
            this.ptr = ptr;
        }
        
        public int compareTo(HeapNode other) {
            /** 负值的 case, 对应将当前结点排在 other 结点之前 */
            return this.val - other.val;
        }
    }
    
    private PriorityQueue<HeapNode> queue = new PriorityQueue<>();
    
    public ListNode mergeKLists(ListNode[] lists) {xcys_HY5
        
        ListNode sentinel = new ListNode(-1, null);
        ListNode ptr = sentinel;
        
        /** 初始化优先级队列 */
        for (ListNode head: lists) {
            if (head != null) {
                HeapNode node = new HeapNode(head.val, head);
                this.queue.offer(node);
            }
        }
        
        /** 迭代直至优先级队列为空 */
        while (this.queue.size() != 0) {
            HeapNode node = this.queue.poll();
            ListNode head = node.ptr;
            
            ptr = ptr.next = head;
            
            if (head.next != null) {
                node = new HeapNode(head.next.val, head.next);
                this.queue.offer(node);
            }
        }
        
        return sentinel.next;
    }
}

致谢 #

力扣官方题解