23. Merge k Sorted Lists

Hard (LinkedIn, Google, Uber, Airbnb, Facebook, Twitter, Amazon, Microsoft)

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

Explaination:

Divide and conquer:

Divide list array into two part in each recursion, merge two list to get the answer.

Priority queue to merge K lists:

Solution 1: Divide & Conquer

public class Solution {

// test case:
// lists is empty
// lists may contain empty ListNode
// list[i] will be equal to null: list[i] == null;

public ListNode mergeKLists(ListNode[] lists) {
    if(lists == null || lists.length == 0) {
        return null;
    }

    return mergeTwoList(lists, 0, lists.length - 1);
}

public ListNode mergeTwoList(ListNode[] lists, int start, int end) {
    if(start > end) {
        return null;
    } else if(start == end) {
        return lists[start];
    }

    int mid = start + (end - start) / 2;
    ListNode l1 = mergeTwoList(lists, start, mid);
    ListNode l2 = mergeTwoList(lists, mid + 1, end);
    ListNode dummy = new ListNode(0);
    ListNode node = dummy;

    while(l1 != null || l2 != null) {
        if(l1 != null && l2 != null) {
            if(l1.val < l2.val) {
                node.next = l1;
                l1 = l1.next;
            } else {
                node.next = l2;
                l2 = l2.next;
            }
        } else if(l1 != null) {
            node.next = l1;
            l1 = l1.next;
        } else {
            node.next = l2;
            l2 = l2.next;
        }

        node = node.next;
    }

    node.next = null;
    return dummy.next;
}

}

Solution 2: PriorityQueue

public class Solution {

// test case:
// lists is empty
// lists may contain empty ListNode
// list[i] will be equal to null: list[i] == null;

public ListNode mergeKLists(ListNode[] lists) {
    if(lists == null || lists.length == 0) {
        return null;
    }

    Queue<ListNode> minHeap = new PriorityQueue<ListNode>(lists.length, new Comparator<ListNode>(){
        public int compare(ListNode n1, ListNode n2) {
            return n1.val - n2.val;
        }
    });

    for(int i = 0; i < lists.length; i++) {
        if(lists[i] != null) {
            minHeap.offer(lists[i]);
        }
    }

    ListNode dummy = new ListNode(0);
    ListNode ln = dummy;

    while(!minHeap.isEmpty()) {
        ListNode node = minHeap.poll();
        ln.next = node;
        ln = ln.next;

        if(node.next != null) {
            minHeap.offer(node.next);
        }
    }

    ln.next = null;
    return dummy.next;
}

}