Merge K Sorted Lists

Merge Two Sorted Lists (LC.21)

Merge two sorted linked lists and return it as a new list.

The new list should be made by splicing together the nodes of the first two lists.

Example

Input: L1 = 1->3->8->11->15->null, L2 = 2->null
Return: 1->2->3->8->11->15->null

Analysis

It should be similar to merge two sort arrays. So we merge two lists until one list is exhausted. Then splice the results with leftovers in either L1 or L2.

Code

public ListNode mergeTwoSortedLists(ListNode l1, ListNode l2) {
    // modifying the head so dummy node 
    ListNode dummy = new ListNode(0);
    ListNode t1 = l1;
    ListNode t2 = l2;
    ListNode current = dummy;
    // merge what they have first
    while (t1 != null && t2 != null) {
        if (t1.val < t2.val) {
            current.next = t1;
            current = current.next;
            t1 = t1.next;
        } else {
            current.next = t2;
            current = current.next;
            t2 = t2.next;
        }
    }
    // splice the rest
    if (t1 != null) current.next = t1;
    if (t2 != null) current.next = t2;
    // return new head
    return dummy.next;
}

Merge K Sorted Lists (LC.23)

Merge k sorted linked lists and return it as one sorted list.

Example

I: [
  2->4->null,
  3->null,
  -1->null
]
O: -1->2->3->4->null

Analysis

The brute force approach is to use a reduction algorithm and reduce the problem to the base case mergeTwoSortedLists. The worst case [1,2,3,4,5],[6],[7],[8],[9] can produce O(N^2) time. The classic k-way merge algorithm can be implemented in three ways. Top-down approach with divide and conquer, BFS approach with a priority queue, and bottom-up approach by merging lists in groups.

Brute Force Reduction

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

    ListNode masterHead = lists[0];
    for (int i = 1; i < lists.length; i++) {
        masterHead = mergeTwoSortedLists(masterHead, lists[i]);
    }
    return masterHead;
}

The brute force received Time Limit Exceeded with a large input of single number lists.

Divide and Conquer

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

private ListNode mergeKSortedLists(ListNode[] lists, int start, int end) {
    // base case
    if (start == end) {
        return lists[start];
    }
    // divide
    int mid = (start + end) / 2;
    // conquer
    ListNode l1 = mergeKSortedLists(lists, start, mid);
    ListNode l2 = mergeKSortedLists(lists, mid+1, end);
    // merge
    return mergeTwoSortedLists(l1, l2);
}

Bottom Up Merge

public ListNode mergeKLists(ListNode[] lists) {
    if (lists == null || lists.length == 0) {
        return null;
    }
    ListNode[] currentLayer = lists;
    ListNode[] nextLayer;
    ListNode tempMerge;
    while (currentLayer.length > 1) {
        // init the next layer
        int halfLength = (currentLayer.length + 1) / 2; // +1 to get enough space
        nextLayer = new ListNode[halfLength];
        // merge in groups of two lists
        for (int i = 0; i + 1 < currentLayer.length; i += 2) {
            tempMerge = mergeTwoSortedLists(currentLayer[i], currentLayer[i+1]);
            nextLayer[i/2] = tempMerge;
        }
        // add the leftover list if currentLen is odd
        if (currentLayer.length % 2 == 1) {
            nextLayer[halfLength - 1] = currentLayer[currentLayer.length - 1];
        }
        // move up to the next layer
        currentLayer = nextLayer;
    }
    return currentLayer[0];
}

Priority Queue Search

Unlike the first two approaches in which we rely on an implicit binary tree structure (height of lg(k) b/c base case is merge2lists), the priority queue uses an explicit full binary tree - heap. We keep the heap fed going down the k lists.

public ListNode mergeKLists(ListNode[] lists) {
    if (lists == null || lists.length == 0) {
        return null;
    }
    final int K = lists.length;
    // modify head so dummy
    ListNode dummy = new ListNode(0);
    // init priority queue
    Comparator<ListNode> lnodeComp = new Comparator<ListNode>() {
        public int compare(ListNode n1, ListNode n2) {
            if (n1 == null) return 1;
            if (n2 == null) return -1;
            return n1.val - n2.val;
        }
    };
    Queue<ListNode> minHeap = new PriorityQueue<>(K, lnodeComp);
    for (int i = 0; i < K; i++) {
        if (lists[i] != null) 
            minHeap.offer(lists[i]);
    }
    // priority queue search
    ListNode travel = dummy;
    while (!minHeap.isEmpty()) {
        ListNode localMin = minHeap.poll();
        travel.next = localMin;
        travel = travel.next;
        if (travel.next != null)
            minHeap.offer(travel.next);
    }
    // return merged list
    return dummy.next;
}

Reading

Wikipedia - External Merge Sort