首页 > itarticle > 104. merge k sorted lists

104. merge k sorted lists

admin 11月 13, 2020 0

explanation

method 1: heap
a) corner case
b) build min heap
c) add heads of each lists into heap
d) curt =poll() and add curt.next into heap
e) time complexity: O(Nlog(N)), N is the number of nodes

code


 * Definition for ListNode.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int val) {
 *         this.val = val;
 *         this.next = null;
 *     }
 * }
 */
public class  {
    
     * @param lists: a list of ListNode
     * @return: The head of one sorted list.
     */
    public ListNode mergeKLists(List<ListNode> lists) {  
        // heap
        // 一定要先判断corner case
        if (lists == null || lists.size() == 0) {
            return null;
        }
        // 1. build a min heap
        PriorityQueue<ListNode> minHeap = new PriorityQueue<>(lists.size(),
        new Comparator<ListNode>() {
            public int compare(ListNode a, ListNode b) {
                return a.val - b.val;
            }
        }
            );
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        // add heads of each list to the heap
        for (int i = 0; i < lists.size(); i++) {
            if (lists.get(i) != null) {
                minHeap.offer(lists.get(i));
            }
        }

        while (minHeap.size() > 0) {
            ListNode curt = minHeap.poll();
            tail.next = curt;
            tail = tail.next;
            if (curt.next != null) {
                minHeap.offer(curt.next);
            }
        }
        return dummy.next;

    }
}