23. Merge k Sorted Lists

Merge_k_sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example:

Input:

[1->4->5, 1->3->4,2->6]

Output:
 1->1->2->3->4->4->5->6

Thoughts:

1. With minheap:

   1. Use minheap to add in head elements first

   2. While heap is not empty, pull the least element o out, then if the next element of the o is not null, add it to the heap.

2. Iterative merging:

Code: Priority Queue T:O(NlogN) Space: O(N)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists == null || lists.length ==0) return null;

        PriorityQueue<ListNode> queue= new PriorityQueue<ListNode>(lists.length, (n1, n2)-> n1.val - n2.val);
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        for(ListNode node : lists){
            if (node != null)
                queue.add(node);
        }
        while(!queue.isEmpty()){
            cur.next = queue.poll(); //link
            cur = cur.next;

            if(cur.next != null){   // put successor in the queue
                queue.add(cur.next);   
            }
        }

        return dummy.next;

    }
}

Code: Iterative Merging T:(NlogN) Space: O(1)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists ==null || lists.length ==0) return null;
        final int n = lists.length;
        for (int b = 1; b < n; b<<=1){
            for(int low = 0; low + b < n; low+= b<<1){
                lists[low]=mergeTwoLists(lists[low], lists[low + b]);
            }
        }

        return lists[0];
    }

    private ListNode mergeTwoLists(ListNode l1, ListNode l2){
        if(l1 == null) return l2;
        if(l2 == null) return l1;
        if(l1.val < l2.val){
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        }
        else{
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }

    }
}