Problem
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Example:
Input:
[
1->1->5,
2->3->4,
2->2
]
Output: 1->1->2->3->4->4->5->6
Solution
Brutal force solution will be create a sorted array then create the linked list with the sorted array. Sorting N elements cost O(NlogN) and we need O(N) space for the array.
The brutal force approach is not optimums because we didn't utilize the feature that the linked lists are already sorted.
We know for sure the minimum element come from the first nodes of the input linked list, so if we add all the k nodes into a priority queue, we can find the minimum node with cost O(klogk).
1-> 1->5,
2-> 3->4,
2-> 2
Once the minimum node is taken, the next minimum could hid in the rest of the k-1 elements, or it could be the next of the minimum node. So we can replace the minimum node with its next node in the priority queue then continue to find the next minimum node. We can continue to do that until the priority queue is empty.
import java.util.*;
public class Solution {
public static void main(String args[]) {
Node head1 = new Node(1, new Node(1, new Node(5, null)));
Node head2 = new Node(2, new Node(3, new Node(4, null)));
Node head3 = new Node(2, new Node(2, null));
//assume Node[] don't have null elements
Node[] arr = new Node[]{head1, head2, head3};
Node result = solve(arr);
printNodes(result);
}
private static Node solve(Node[] arr) {
Node head = null;
Node tail = null;
PriorityQueue<ValToLLIndex> pq = new PriorityQueue<>((o1, o2) -> o1.val - o2.val);
for(int i = 0; i < arr.length; i++) {
pq.add(new ValToLLIndex(arr[i].val, i)); //3-1,5-0,,
arr[i] = arr[i].next;
}
while(!pq.isEmpty()) {
ValToLLIndex valToLLIndex = pq.poll(); //2-2
if(head == null) {
head = new Node(valToLLIndex.val, null);
tail = head;
} else {
tail.next = new Node(valToLLIndex.val, null);
tail = tail.next;
}
int index = valToLLIndex.index;//0
if(arr[index] != null) {
pq.add(new ValToLLIndex(arr[index].val, index));
arr[index] = arr[index].next;
}
}
return head;
}
static class ValToLLIndex {
int val;
int index;
public ValToLLIndex(int val, int index) {
this.val = val;
this.index = index;
}
}
private static void printNodes(Node head) {
while(head != null) {
System.out.print(head.val + "->");
head = head.next;
}
System.out.println("null");
}
static class Node {
int val;
Node next;
public Node(int val, Node next) {
this.val = val;
this.next = next;
}
}
}
The time complexity is O(Nklogk) because for each of the N node, we need to add it to the priority queue of size k in order to find the next minimum. The size k priority queue add takes O(klogk), poll takes O(1).
The space complexity is O(k), which is the size of the priority queue.
