Leetcode --- Merge k Sorted Lists
===
## Description
You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.
Merge all the linked-lists into one sorted linked-list and return it.
### Examples
* Ex1:
**Input**: lists = [[1,4,5],[1,3,4],[2,6]]
**Output**: [1,1,2,3,4,4,5,6]
**Explanation**: The linked-lists are:
[
1->4->5,
1->3->4,
2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6
* Ex2:
**Input:** lists = []
**Output:** []
* Ex3:
**Input**: lists = [[]]
**Output**: []
### Constraints
* k == lists.length
* 0 <= k <= 10^4^
* 0 <= lists[i].length <= 500
* -10^4^ <= lists[i][j] <= 10^4^
* lists[i] is sorted in ascending order.
* The sum of lists[i].length won't exceed 10^4^.
## Solutions
* **Method 1 : Brute Force**
The idea is that I go through all the nodes in the list and save their values into a new array,and afterwards the whole problem becomes a very easy one at the moment,I just need to sort the values in the array and put these values into each node in the new linked list.
### implement code
```java=
/**
* 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;
for(int i = 0 ; i< lists.length ;i++)
{
if(lists[i] != null)
break;
if(i == lists.length -1 )
return null;
}
//get the size of the list
//get the value,which is in the list, to store it in the array
int[] tmp = new int[countsize(lists)];
getvalue(lists,tmp);
//sort
Arrays.sort(tmp);
//put the value,which is in the array, into the nodes,which is in the list
ListNode ans = new ListNode();
ListNode head = ans;
for(int i =0 ; i< tmp.length ;i++)
{
head.val = tmp[i];
if(i != tmp.length-1)
{
head.next =new ListNode();
head =head.next;
}
}
return ans;
}
public int countsize(ListNode[] lists)
{
int k =0;
for(int i =0 ;i< lists.length ; i++)
{
ListNode tmp = lists[i];
while(tmp != null)
{
k++;
tmp =tmp.next;
}
}
return k;
}
public void getvalue(ListNode[] lists,int[] arr)
{
for(int i =0,k=0 ;i< lists.length ; i++)
{
ListNode tmp = lists[i];
while(tmp != null)
{
arr[k] = tmp.val;
k++;
tmp =tmp.next;
}
}
}
}
```
### Complexity Analysis
* Time Complexity
The getvalue function is executed n times in the for and while loops, where n is the total number of nodes,in term of Big O notation is O(n),and the countsize function is also exactly the same,so O(n) as well.
The sort function is costing O(nlogn) in the best case and worse case.
Finally, I put the values into the nodes and traverse the entire array, the cost is still O(n).
**Total time complexity**
O(n) + O(n) + O(nlogn) + O(n) = ==O(nlogn)== where n is the total number of nodes in the list.
* Space Complexity
I created an array to hold all the values in the node,its size is n,where n is number of nodes in the list,so O(n).
What I also allocated is the answer list, which has the same number of nodes as the array,so O(n).
**Total Space Complexity**
O(n) + O(n) = ==O(n)==,where n is number of the nodes in the list.
### Submission on leetcode
Runtime: **2 ms, 89.17%**
Memory Usage: **40.3 MB, 81.96%**
---
* **Method 2 : Compare one by one**
The idea is that I find the minimum value from ListNode array by comparing,then I can put this minimum value in my answer list,and I move the next pointer from the list that has the minimum value.Therefore, I can iteratively perform the above idea and finally find an answer list.
### Implement code
```java=
/**
* 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) {
//find the biggest vaule at node in every lists
if(lists.length == 0)
return null;
boolean flag = true;
for(int i = 0 ; i < lists.length ; i++)
{
if(lists[i] != null)
{
flag =false ;
break;
}
}
if(flag)
return null;
ListNode ans = new ListNode();
ListNode head =ans;
int MIN_pointer =0;
int countNUll = 0;
while(countNUll < lists.length)
{
int min =Integer.MAX_VALUE;
countNUll =0;
boolean change = false;
for(int i = 0 ; i< lists.length ; i++)
{
if(lists[i] == null )
{
countNUll ++;
continue;
}
if(lists[i].val < min)
{
change = true;
min = lists[i].val;
MIN_pointer =i;
}
}
if(change)
{
head.next = new ListNode(min);
lists[MIN_pointer] = lists[MIN_pointer].next;
head =head.next;
}
}
return ans.next ;
}
}
```
### Complexity Analysis
* Time Complexity
The inner for loop from line 39 to line 53 in the code finds the minimum value of all nodes in the list,so I compare at most n nodes,its cost is O(k),where k is lists.length.
The outer while loop is gonna stop if all lists are null,in other words,it will execute all nodes in the list,therefore,its cost is O(n) where n is total number of nodes.
**Total time complexity**
O(k) * O(n) = ==O(kn)==,where k is lists.length and n is number of nodes in the list.
* Space Complexity
I only created an answer list,its size is the number of all nodes in the input list,its cost is O(n) where n is total number of nodes.
**Total space complexity**
==O(n)== where n is number of nodes in the list.
### Submission on leetcode
Runtime: 433 ms
Memory Usage: 44.7 MB
---
* **Method 3 : Optimize Approach 2 by Priority Queue**
Here is a way to accelerate the comparison part of method 2,it uses the specific data structure,Priority Queue.
The time complexity of the comparison part can be improved from O(n) to O(logn)
### Implement code
```java=
/**
* 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; }
* }
*/
import java.util.*;
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
Comparator<ListNode> cmp = new Comparator<ListNode>(){
@Override
public int compare(ListNode l1,ListNode l2)
{
return l1.val - l2.val;
}
};
PriorityQueue<ListNode> pq = new PriorityQueue<ListNode>(cmp);
for(int i = 0 ; i< lists.length ; i++)
{
if(lists[i] != null)
pq.offer(lists[i]);
}
ListNode ans = new ListNode();
ListNode head =ans;
while(pq.size() != 0)
{
ListNode tmp = pq.poll();
head.next = tmp;
head = head.next ;
tmp =tmp.next;
if(tmp != null)
pq.offer(tmp);
}
return ans.next;
}
}
```
### Complexity Analysis
* Time Complexity
First of all,I invite the heads of all nodes in the list to our priority queue,its cost is O(k) where k is lists.length.
And afterwards,I take the minumum value from priority queue and invite the next node into my priority queue,so these are O(logk) + O(logk),and these above operations must be performed iteratively until all nodes are out of the priority queue,therefore,they are executed n-k times where n is number of nodes and k is lists.length,so the Big O is O(n-k) which is almost equal to O(n),the entire while loop cost O(logk) * O(n) = O(nlogk)
**Total time complexity**
O(k) + O(nlogk) = ==O(nlogk)== where k is lists.length and n is number of nodes in list.
* Space Complexity
I created a priority queue and its size at most is k where k is lists.length,and I also created an answer list,it must be the same size as the number of nodes in the input list
**Total space complexity**
O(k) + O(n) = ==O(n)== where n is number of nodes in list.
### Submission on leetcode
Runtime: **3 ms, faster than 82.65%** of Java online submissions for Merge k Sorted Lists.
Memory Usage: **40.7 MB, less than 55.72%** of Java online submissions for Merge k Sorted Lists.
###### tags: `Leetcode` `LinkedList` `Hard` `Priority queue`
Sign in with Wallet
Connect another wallet