Merge k Sorted Lists

LeetCode Q 23 - Merge k Sorted Lists

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

Solution

k: number of sorted linked lists;
N: Total number of nodes in all k linked lists.

Method 1: Heap Sort

Time Complexity: O(Nlogk)

The comparison cost will be reduced to O(log k) for every pop and insertion to priority queue. But finding the node with the smallest value just costs O(1) time.

Space Complexity: O(N) + O(k)

O(N): Creating a new linked list costs space, i.e. the result.
O(k): Build heap.

Code:

public ListNode mergeKLists(ListNode[] lists) {
	if (lists == null || lists.length == 0) return null;
	// build the heap
	PriorityQueue<ListNode> pq = new PriorityQueue<>((a,b) -> (a.val - b.val));
	for (ListNode node: lists) {
		if (node != null) pq.offer(node);
	}

	ListNode dummy = new ListNode(-1), prev = dummy;
	while (!pq.isEmpty()) {
		ListNode temp = pq.poll();
		prev.next = temp;
		prev = temp;
		if (temp.next != null) pq.offer(temp.next);
	}
	
	return dummy.next;
}

Method 2: Merge Lists with Divide And Conquer

Time Complexity: O(Nlogk)

We can merge two sorted linked list in O(n) time, where n is the total number of two lists.
Sum up the merge process and we can get O(Nlogk).

Space Complexity: O(1)
No extra space is required.

Code:

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

private ListNode merge(ListNode[] lists, int left, int right) {
	if (left > right) return null;
	if (left == right) return lists[left];
	int mid = left + (right - left) / 2;
	ListNode node1 = merge(lists, left, mid);
	ListNode node2 = merge(lists, mid + 1, right);
	return mergeHelper(node1, node2);
}

private ListNode mergeHelper(ListNode node1, ListNode node2) {
    if (node1 == null) return node2;
    if (node2 == null) return node1;
    ListNode dummy = new ListNode(-1), prev = dummy;
    while (node1 != null && node2 != null) {
        if (node1.val < node2.val) {
            prev.next = node1;
            prev = prev.next;
            node1 = node1.next;
        } else {
            prev.next = node2;
            prev = prev.next;
            node2 = node2.next;
        }
    }
    if (node1 == null) prev.next = node2;
    if (node2 == null) prev.next = node1;
    return dummy.next;
}