---
# System prepended metadata

title: Leetcode --- Merge k Sorted Lists
tags: [Leetcode, Hard, LinkedList, Priority queue]

---

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`

