Understand the problem:
The question asks for merging k sorted linked list and return it as one sorted list. It is an extension of merging the two sorted linked list but more complicated.
The question also asked for analyzing and describing the complexity.
Naive Solution:
One naive solution is to merge two linked list at first, then merge it with next linked list until we are done with all the input linked list.
Code (Java):
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode mergeKLists(ArrayList<ListNode> lists) {
if (lists == null || lists.size() == 0) return null;
if (lists.size() == 1) return lists.get(0);
int numLists = lists.size();
ListNode newHead = new ListNode(0);
ListNode l1, l2;
for (int i = 1; i < numLists; i++) {
if (i == 1) {
l1 = lists.get(0);
} else {
l1 = newHead;
}
l2 = lists.get(i);
newHead = mergeTwoLists(l1, l2);
}
return newHead;
}
// Merge two sorted linked lists
private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode p1 = l1;
ListNode p2 = l2;
ListNode head = new ListNode(0);
ListNode p = head;
while (p1 != null && p2 != null) {
if (p1.val <= p2.val) {
p.next = p1;
p1 = p1.next;
} else {
p.next = p2;
p2 = p2.next;
}
p = p.next;
}
if (p1 != null) p.next = p1;
else if (p2 != null) p.next = p2;
return head.next;
}
}
Analysis:
Now we discuss the complexity of the algorithm. Suppose we have k sorted lists to merge, each has size of n. When we merge the first two lists, the time complexity is O(2n), then merge with the third one, the time complexity is O(2n + n) = O(3n), the fourth one, O(3n + n) = O(4n)... the kth one O(kn). So the total time complexity for merging k sorted lists is O(2n) + O(3n) + ... + O(kn) = O(k^2 n). The space complexity is O(1).
A Better Solution:
A better solution is to use the idea of merge sort, i.e, we divide the k linked list into k/2, then k/4, until there is only one or two linked list. So the time complexity would be O(klogk * n).
Code (Java):
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode mergeKLists(ArrayList<ListNode> lists) {
if (lists == null || lists.size() == 0) return null;
if (lists.size() == 1) return lists.get(0);
int numLists = lists.size();
return merge(lists, 0, numLists - 1);
}
private ListNode merge(ArrayList<ListNode> lists, int lo, int hi) {
if (lo == hi) return lists.get(lo);
int mid = (lo + hi) / 2;
ListNode l1 = merge(lists, lo, mid);
ListNode l2 = merge(lists, mid + 1, hi);
return mergeTwoLists(l1, l2);
}
private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode p1 = l1;
ListNode p2 = l2;
ListNode head = new ListNode(0);
ListNode p = head;
while (p1 != null && p2 != null) {
if (p1.val <= p2.val) {
p.next = p1;
p1 = p1.next;
} else {
p.next = p2;
p2 = p2.next;
}
p = p.next;
}
if (p1 != null) p.next = p1;
else if (p2 != null) p.next = p2;
return head.next;
}
}
Another Solution:
Another solution is to maintain a size of k priority queue. Priority queue is actually a heap. So initially we add the first element of each linked list into the queue. And remove the minimum element from the queue, insert the next one, until the queue is empty.
Code (Java):
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode mergeKLists(ArrayList<ListNode> lists) {
if (lists == null || lists.size() == 0) return null;
if (lists.size() == 1) return lists.get(0);
PriorityQueue<ListNode> pq = new PriorityQueue<ListNode> (lists.size(), new ListNodeComparator());
// Add first element of each list into the queue
for (ListNode x : lists) {
if (x != null) pq.add(x);
}
// retrive the minimum element from the queue and insert the next one
ListNode head = new ListNode(0);
ListNode p = head;
while (pq.size() > 0) {
ListNode temp = pq.poll();
p.next = temp;
if (temp.next != null) pq.add(temp.next);
p = p.next;
}
return head.next;
}
private class ListNodeComparator implements Comparator<ListNode> {
public int compare(ListNode l1, ListNode l2) {
return l1.val - l2.val;
}
}
}
Discussion:
Regarding the heap operations, inserting an element into the heap requires an average O(log k) time, k is the number of elements in the heap. Poll the minimum is O(1) operation since it is at the top of the heap. Since we inserted totally O(n * k) elements into the heap, the total time complexity is O(klogk * n), the same as solution 2. The space complexity is O(k) since we maintained a k-sized heap to store the minimum k elements.
Summary:
In this post, we learned how to merge k sorted linked list into one. It is a very important operation it real applications. For instance, given k sorted entries from k servers, we wanna merge them into one sorted entries at the centralized server. The first solution is straight-forward, but for the k is very large, it is clearly inefficient. The solution two is based on the idea of merge sort. It divides-and-concur the k lists into two or one and then merge together. Note the recursion implementation. Solution three is neat but requires deep understanding of the priority queue.
What's the space complexity of the Divide an Conquer approach?
ReplyDelete