Problem
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
Solution
brutal force solution is to traversal all the linked lists, create an array, sort the array, then create a new linked list.
The time cost is O(NlogN), space cost is O(N)
we can also put the first k nodes into a priority queue, then take one at a time, push the next into the queue until done.
import java.util.*;
class KLinkedListsMerge {
public static Node merge(Node[] nodes) {
Node kHead = new Node(-1, null);
Node tail = kHead;
PriorityQueue<Node> pq = new PriorityQueue<>((i, j) -> i.value - j.value);
for(Node head : nodes)
pq.add(head);
while(!pq.isEmpty()) {
Node head = pq.poll();
if(head.next != null)
pq.add(head.next);
head.next = null;
tail.next = head;
tail = head;
}
return kHead;
}
private static class Node {
int value;
Node next;
public Node(int value, Node next) {
this.value = value;
this.next = next;
}
}
public static void main(String...args) {
Node[] nodes = new Node[3];
//1->4->5
nodes[0] = new Node(1, new Node(4, new Node(5, null)));
nodes[1] = new Node(1, new Node(3, new Node(4, null)));
nodes[2] = new Node(2, new Node(6, null));
Node head = merge(nodes);
head = head.next;
while(head.next != null) {
System.out.print(head.value + " -> ");
head = head.next;
}
System.out.println("null");
}
}
class KLinkedListsMerge {
public static Node merge(Node[] nodes) {
Node kHead = new Node(-1, null);
Node tail = kHead;
PriorityQueue<Node> pq = new PriorityQueue<>((i, j) -> i.value - j.value);
for(Node head : nodes)
pq.add(head);
while(!pq.isEmpty()) {
Node head = pq.poll();
if(head.next != null)
pq.add(head.next);
head.next = null;
tail.next = head;
tail = head;
}
return kHead;
}
private static class Node {
int value;
Node next;
public Node(int value, Node next) {
this.value = value;
this.next = next;
}
}
public static void main(String...args) {
Node[] nodes = new Node[3];
//1->4->5
nodes[0] = new Node(1, new Node(4, new Node(5, null)));
nodes[1] = new Node(1, new Node(3, new Node(4, null)));
nodes[2] = new Node(2, new Node(6, null));
Node head = merge(nodes);
head = head.next;
while(head.next != null) {
System.out.print(head.value + " -> ");
head = head.next;
}
System.out.println("null");
}
}
The time cost is bounded by the priority queue, the queue size is k after initialization, then add each element need logk time to restore the order. The total time cost is O(Nlogk). Space cost is the O(k) which is the priority queue size.
