# Merge k Sorted Lists

### **Problem Statement:-**

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.*

**Link:** [https://leetcode.com/problems/merge-k-sorted-lists/](https://leetcode.com/problems/merge-k-sorted-lists/)

### **Problem Explanation with examples:-**

**Example 1**

```markdown
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
```

**Example 2**

```markdown
Input: lists = []
Output: []
Explanation: The input list is empty, so the answer is also empty.
```

**Example 3**

```markdown
Input: lists = [[]]
Output: []
Explanation: The input contains one empty list, so the answer is also empty. 
```

**Example 4**

```markdown
Input: lists = [[6,7,8,9,10],[1,2,3,4,5]]
Output: [1,2,3,4,5,6,7,8,9,10]
Explanation: The linked-lists are: 1->2->3->4->5, 6->7->8->9->10. After merging them, we get 1->2->3->4->5->6->7->8->9->10.
```

**Constraints**

* `k == lists.length`
    
* `0 <= k <= 10<sup>4</sup>`
    
* `0 <= lists[i].length <= 500`
    
* `-10<sup>4</sup> <= lists[i][j] <= 10<sup>4</sup>`
    
* `lists[i]` is sorted in **ascending order**.
    
* The sum of `lists[i].length` will not exceed `10<sup>4</sup>`.
    

### Intuition:-

* The non-complex way would be to put all the values separately with their frequencies out of all the lists and then create a new linked list in sorted order.
    
* For storing the values and their frequencies, a dictionary or another list can be used along with their frequencies.
    

### Solution:-

* Create a dictionary to store the values and their frequencies.
    
* Traverse through all the lists and store the values and their frequencies in the dictionary.
    
* Sort the dictionary in ascending order based on the keys.
    
* Create a new linked list head and initialize a temp variable to it.
    
* Traverse through the dictionary and run a while loop which will run for the number of times the value is present in the dictionary.
    
* Create a new node with the value and append it to the linked list.
    
* Finally set the next of the last node to None.
    
* Return the `head.next` of the linked list as the 1st node is a dummy node.
    

### Code:-

JAVA Solution

```java
import java.util.*;

public class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        Map<Integer, Integer> mp = new HashMap<>();
        for (ListNode i : lists) {
            ListNode temp = i;
            while (temp != null) {
                if (!mp.containsKey(temp.val)) {
                    mp.put(temp.val, 1);
                } else {
                    mp.put(temp.val, mp.get(temp.val) + 1);
                }
                temp = temp.next;
            }
        }
        
        Map<Integer, Integer> mps = new TreeMap<>(mp);
        ListNode head = new ListNode(0);
        ListNode temp = head;
        for (Map.Entry<Integer, Integer> entry : mps.entrySet()) {
            int i = entry.getKey();
            int z = entry.getValue();
            while (z > 0) {
                ListNode x = new ListNode(i);
                temp.next = x;
                temp = temp.next;
                z--;
            }
        }
        
        temp.next = null;
        return head.next;
    }
}
```

Python Solution

```python
class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        mp = {}
        for i in lists:
            temp = i
            while temp:
                if mp.get(temp.val,-1) == -1:
                    mp[temp.val] = 1
                else:
                    mp[temp.val] += 1
                temp = temp.next
        
        mps = OrderedDict(sorted(mp.items()))
        head = ListNode(0)
        temp = head
        for i in mps:
            z = mps[i]
            while z > 0:
                x = ListNode(i)
                temp.next = x
                temp = temp.next
                z -= 1
        
        temp.next = None

        return head.next
```

### Complexity Analysis:-

**TIME**:-

Time complexity is **O(n\*m)** where n is the number of lists and m is the maximum number of nodes in a list.

**SPACE**:-

Space complexity is **O(n)**, as we are using a dictionary to store the values and the maximum keys we can have is n.

### References:-

* [**Merge Sort**](https://www.geeksforgeeks.org/merge-sort/)
    
* [**Linked List**](https://www.geeksforgeeks.org/data-structures/linked-list/)
    

### Connect with me:-

* [**Twitter**](https://twitter.com/lakshit_cs)
    
* [**Github**](https://github.com/Lakshit-Chiranjiv)
    
* [**LinkedIn**](https://www.linkedin.com/in/lakshit-chiranjiv-sagar-4b0b15198/)