Leetcode 23 Merge k Sorted Lists
The problem description is as follow:
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
* Definition for singly-linked list.
* public class ListNode {
* ListNode(int x) { val = x; }
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
Merge-Sort Approach
Edit Merge k Sorted Lists on GitHub
It is quite intuitive to think about merge-sort. This problem is a simple transform of the original merge sort problem. We just have to divide those k sorted lists into smaller groups, and do the sort and merge.
public ListNode mergeKLists(ListNode[] lists) {
if(lists==null || lists.length==0)
return mergeSort(lists,0,lists.length-1);
private ListNode mergeSort(ListNode[] lists, int l, int r) {
return merge(mergeSort(lists,l,m),mergeSort(lists,m+1,r));
private ListNode merge(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
while(l1!=null && l2!=null) {
public class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if(lists==null || lists.length==0)
return null;
return mergeSort(lists,0,lists.length-1);
}
private ListNode mergeSort(ListNode[] lists, int l, int r) {
if(l<r) {
int m = (l+r)/2;
return merge(mergeSort(lists,l,m),mergeSort(lists,m+1,r));
}
return lists[l];
}
private ListNode merge(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
dummy.next = l1;
ListNode cur = dummy;
while(l1!=null && l2!=null) {
if(l1.val<l2.val) {
l1 = l1.next;
}
else {
ListNode next = l2.next;
cur.next = l2;
l2.next = l1;
l2 = next;
}
cur = cur.next;
}
if(l2!=null)
cur.next = l2;
return dummy.next;
}
}
public class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if(lists==null || lists.length==0)
return null;
return mergeSort(lists,0,lists.length-1);
}
private ListNode mergeSort(ListNode[] lists, int l, int r) {
if(l<r) {
int m = (l+r)/2;
return merge(mergeSort(lists,l,m),mergeSort(lists,m+1,r));
}
return lists[l];
}
private ListNode merge(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
dummy.next = l1;
ListNode cur = dummy;
while(l1!=null && l2!=null) {
if(l1.val<l2.val) {
l1 = l1.next;
}
else {
ListNode next = l2.next;
cur.next = l2;
l2.next = l1;
l2 = next;
}
cur = cur.next;
}
if(l2!=null)
cur.next = l2;
return dummy.next;
}
}
Similar to the analysis in Leetcode 148 Sort List, assume the maximum length of every list is
n
n
, the time complexity is function
T(k)
T(k)
, then we have
T(k) = T(k/2) + O(n*k)
T(k) = T(k/2) + O(n*k)
.
According to Master Theorem,
T(k) = O(n*klogk)
T(k) = O(n*klogk)
. The space complexity is
O(logk)
O(logk)
, which is the depth of our recursive call.
Heap Approach
We can maintain a heap of size k and use heap-sort to return the smallest number in heap.
1. Put first number of each sorted list into the k-size heap.
2. Pop the smallest number, say x in heap.
3. Push x.next into the heap to maintain size.
4. Pop a new smallest number ...
1. Put first number of each sorted list into the k-size heap.
2. Pop the smallest number, say x in heap.
3. Push x.next into the heap to maintain size.
4. Pop a new smallest number ...
1. Put first number of each sorted list into the k-size heap.
2. Pop the smallest number, say x in heap.
3. Push x.next into the heap to maintain size.
4. Pop a new smallest number ...
Note that we can implement the heap with
PriorityQueue
PriorityQueue
in Java:
public ListNode mergeKLists(ListNode[] lists) {
//PriorityQueue is a heap that use heap-sort
PriorityQueue<ListNode> heap = new PriorityQueue<ListNode>(lists.length,
new Comparator<ListNode>() {
public int compare(ListNode a, ListNode b) {
//add first node of each list to the heap
for (ListNode list : lists) {
ListNode head = new ListNode(0);
ListNode p = head; // serve as a helper dummy node
while (heap.size() > 0) {
ListNode temp = heap.poll();
//poll() retrieves and removes the head of the heap
//keep adding next element of each list
public class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists.length == 0)
return null;
//PriorityQueue is a heap that use heap-sort
PriorityQueue<ListNode> heap = new PriorityQueue<ListNode>(lists.length,
new Comparator<ListNode>() {
public int compare(ListNode a, ListNode b) {
return a.val-b.val;
}
});
//add first node of each list to the heap
for (ListNode list : lists) {
if (list != null)
heap.add(list);
}
ListNode head = new ListNode(0);
ListNode p = head; // serve as a helper dummy node
while (heap.size() > 0) {
ListNode temp = heap.poll();
//poll() retrieves and removes the head of the heap
p.next = temp;
//keep adding next element of each list
if (temp.next != null)
heap.add(temp.next);
p = p.next;
}
return head.next;
}
}
public class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists.length == 0)
return null;
//PriorityQueue is a heap that use heap-sort
PriorityQueue<ListNode> heap = new PriorityQueue<ListNode>(lists.length,
new Comparator<ListNode>() {
public int compare(ListNode a, ListNode b) {
return a.val-b.val;
}
});
//add first node of each list to the heap
for (ListNode list : lists) {
if (list != null)
heap.add(list);
}
ListNode head = new ListNode(0);
ListNode p = head; // serve as a helper dummy node
while (heap.size() > 0) {
ListNode temp = heap.poll();
//poll() retrieves and removes the head of the heap
p.next = temp;
//keep adding next element of each list
if (temp.next != null)
heap.add(temp.next);
p = p.next;
}
return head.next;
}
}
In case you are not familiar with Heap and HeapSort:
- Get the smallest element in the heap requires
O(1)
O(1)
- Put a new element in the heap of size k requires
O(k)
O(k)
Since we have
n*k
n*k
elements in total, the total time complexity will be
O(nk*logk)
O(nk*logk)
. The space complexity will be the size of heap
O(k)
O(k)
.
Further Thoughts
Using heap to get the smallest/biggest single number or top K biggest/smallest numbers is very useful in real life, especially in big data area. If you want to know the hottest 10 topics, musics in billions of them, maintaining a heap is one of the best ways to do it. I will further discuss this problem in the future.