Problem:
Given k singly linked sorted lists merge them together into one sorted list.
For example,
given the below lists:
[[1,4,5],[1,3,4],[2,6]]
merge them into [1,1,2,3,4,4,5,6]
Try out the solution here:
https://leetcode.com/problems/merge-k-sorted-lists/
Solution:
Hint:
- You can use the brute force approach by traversing each element in each list , put the value in an integer array , sort the array and then for each element in the array create a linked list node and connect them all together
- Or you can compare the head of each linked list , store the smallest in a node and continue the same after moving the smallest node pointer to its next element.
- Or you can use a priority queue , add the lists to it , pop out the smallest linked list , remove its head and add it again to the list. Every time you pop a node add it to the result list.
- Or you can merge two lists at a time using the merge two lists algorithm .
- Or you can improve the previous algorithm through divide and conquer by merging only alternative lists at a time.
Let’s look at all of them .
Brute force
In this case , you copy all the node values into an array.
You then sort the array.
Then for each element in the array , you create a node and link them all together.
Here is the code:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
List<Integer> list = new ArrayList<Integer>();
int index = 0;
for(ListNode l:lists){
while(l != null){
list.add(l.val);
l = l.next;
}
}
//pointer to the first node
ListNode head = new ListNode();
//pointer to traverse through the linked list
ListNode current = head;
Collections.sort(list);
for(Integer i:list){
current.next = new ListNode(i);
current = current.next;
}
return head.next;
}
}
Time complexity:
Let n be the number of nodes.
For storing each node value in an array , the time complexity is O(n)
For the sorting of the array , time complexity depends on the sorting algorithm.
Lets assume the best case and use O(nlogn)
Creating a node for each element in the array for the final result takes O(n) time.
So total time complexity is O( n + nlogn + n) which can be considered as O(n)
Space complexity:
Creating a output node for each node results in O(n) space complexity.
Comparing head nodes:
In this method ,
Compare the head nodes of all the lists.
Create a current pointer and point it to the smallest node.
Move the pointer to the head node of the smallest node got above to the next node.
Again find the smallest head node and add it to current pointer.
Do this until all the elements in the lists are processed.
Here is the code:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
ListNode head = new ListNode();
ListNode current = head;
//until all the lists are processed
while(true){
int min = Integer.MAX_VALUE;
int minIndex = 0;
boolean noMoreLists = true;
for(int i=0;i<lists.length;i++){
if(lists[i] != null){
if(lists[i].val < min){
min = lists[i].val;
minIndex = i;
}
// the current linked list has some elements
noMoreLists = false;
}
}
// there is no more elements in any of the lists
if(noMoreLists){
break;
}
//point current pointer to the smallest head node
current.next = lists[minIndex];
current = current.next;
// advance the pointer to the smallest head node to the next node to continue the algorithm
lists[minIndex] = lists[minIndex].next;
}
return head.next;
}
}
Time complexity:
To select each node for the output result we iterate through all the k sorted lists.
So if there are n nodes , time complexity is O(kn).
Space complexity:
Space complexity is O(1) since we dont use any additional storage in proportion to the input. Just few pointers.
Using Priority Queue
Priority Queue is a data structure which automatically sorts the elements added to it according to a priority.
For example ,
If you create a priority queue of integers , the default priority is sorting based on the numerical value in the ascending order. The smallest element will be at the top.
You can override this priority using comparators.
In our case we will create a priority queue of LinkedLists
We set the priority by creating a comparator which compares the values of the head nodes of the linked lists added to the queue.
So the linked list with the smallest head node will be at the top.
To merge the k sorted lists,
Add each of the k lists to the queue.
The list with the smallest head node will be at the top now.
Pop it out, then pop out the head node , assign it to “current” pointer .
Put the linked list again into the queue.
This time the head node will be different so the queue will sort the lists according to the current head values.
This way again you will have the list with the smallest head node at the top.
You can then pop it again and continue the algorithm as before until all the elements are popped out.
Here is the code:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if(lists == null) return null;
if(lists.length == 0) return null;
PriorityQueue<ListNode> queue = new PriorityQueue<ListNode>(new Comparator<ListNode>(){
@Override
public int compare(ListNode l1,ListNode l2){
if(l1.val < l2.val){
return -1;
}else if(l1.val == l2.val){
return 0;
}else{
return 1;
}
}
});
ListNode head = new ListNode();
ListNode current = head;
for(ListNode l:lists){
if(l!=null)
queue.add(l);
}
while(!queue.isEmpty()){
ListNode node = queue.poll();
current.next = node;
current = current.next;
if(node.next!=null){
queue.add(node.next);
}
}
return head.next;
}
}
Time complexity:
Adding each list takes O(k) time complexity.
Popping each node out of the queue takes O(n) time complexity.
While popping out the priority queue shuffles internally to keep the smallest list at the top.
This takes O(logK) time complexity.
So the total time complexity is O( k + nlogk) which can be considered as O(nlogk)
Space complexity:
All the nodes are pushed into the queue so space complexity is O(n)
Merge two lists at a time:
In this approach ,
you merge the first list and the second list .
Then you merge the merged list with the third list and so on until you reach the end of the k lists.
For merging two lists , you use the algorithm already discussed in the post:
Here is the code:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if(lists == null) return null;
if(lists.length == 0) return null;
ListNode mergedList = lists[0];
for(int i=1;i<lists.length;i++){
mergedList = mergeTwoLists(mergedList,lists[i]);
}
return mergedList;
}
public ListNode mergeTwoLists(ListNode list1,ListNode list2){
ListNode head = new ListNode();
ListNode tail = head;
while(list1!= null && list2!=null){
if(list1.val < list2.val){
tail.next = list1;
list1 = list1.next;
}else{
tail.next = list2;
list2 = list2.next;
}
tail = tail.next;
}
if(list1 == null){
tail.next = list2;
}
if(list2 == null){
tail.next = list1;
}
return head.next;
}
}
Time complexity:
Merging two sorted lists take O(n) time where n is the total number of nodes in both the lists.
We do k merges here where k is the length of the list.
So time complexity is O(kn)
Space complexity:
There is no extra space complexity that grows in proportion to the input , only few pointers used here so space complexity is O(1)
Merging two lists at a time using Divide and Conquer:
In the above approach , you do as many number of merges as there are number of linked lists.
This time complexity can be improved by merging alternate pair of lists at a time.
So if there are six linked lists in the list of linked lists,
you merge 1st and 2and list
then you merge 3rd and 4th list
then you merge 5th and 6th list
You have got 3 merged lists now.
Again you merge the alternate pairs.
you merge the 1st and 2and list
3rd list does not have a pair so you leave it as such.
After the above two steps , you have 2 merged lists.
You merge them again and you get the final merged list.
Here is a diagram to visualize:
Each circle represents a linked list.
The number inside the list represents the index position.
As you see the alternate linked lists are merged and the result is stored in the index of the first list in the pair.
If you notice after each round the interval between two linked lists get doubled.
We will use this logic in our code:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if(lists.length == 0) return null;
int interval = 1;
while(interval < lists.length){
for(int i=0;i+interval < lists.length ; i = i+(interval*2)){
lists[i] = mergeTwoLists(lists[i],lists[i+interval]);
}
interval = interval *2;
}
return lists[0];
}
public ListNode mergeTwoLists(ListNode list1,ListNode list2){
ListNode head = new ListNode();
ListNode tail = head;
while(list1!= null && list2!=null){
if(list1.val < list2.val){
tail.next = list1;
list1 = list1.next;
}else{
tail.next = list2;
list2 = list2.next;
}
tail = tail.next;
}
if(list1 == null){
tail.next = list2;
}
if(list2 == null){
tail.next = list1;
}
return head.next;
}
}
Time complexity:
Instead of k merges we just do logk merges in this approach.
So time complexity is O(nlogk) where n is the total number of nodes.
That’s it!
Leave a Reply