[LeetCode] Problem 23 - Merge K Sorted Linked 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

O(nklogk) runtime, O(k) space – Heap

public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

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

    PriorityQueue<ListNode> minHeap = new PriorityQueue<>(lists.length, (o1, o2) -> o1.val - o2.val);

    ListNode head = new ListNode(0);
    ListNode current = head;

    for (ListNode node : lists) {
        if (node != null)
            minHeap.add(node);
    }

    while (!minHeap.isEmpty()) {
        current.next = minHeap.poll();;
        current = current.next;

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

    return head.next;
}

O(nklogk) runtime, O(1) space – Divide and conquer using two way merge

public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

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

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

private ListNode partition(ListNode[] lists, int start, int end) {
    if (start == end)
        return lists[start];

    int mid = (start + end) >> 1;

    ListNode left = partition(lists, start, mid);
    ListNode right = partition(lists, mid + 1, end);

    return mergeTwoLists(left, right);
}

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;
    }
}