# Merge k Sorted Lists Leetcode Solution

Difficulty Level Hard
Divide and Conquer Heap Linked-List Shopee tiktok TuSimple Walmart Global techViews 2615

## Problem Statement

The Merge k Sorted Lists LeetCode Solution – “Merge k Sorted Lists” states that given the array of k linked lists, where each linked list has its values sorted in ascending order. We need to merge all the k-linked lists into one single linked list and return the head of the linked list.

## Example:

`Input:  lists = [[1,4,5],[1,3,4],[2,6]]`
`Output: [1,1,2,3,4,4,5,6]`

Explanation:

• Consider all values in ascending order: [1, 1, 2, 3, 4, 4, 5, 6].
• We need to form a linked list with the above values.
`Input:  lists = []`
`Output: []`

Explanation:

• The input array is empty, return the null pointer as the head of the linked list.

## Approach

### Idea:

1. The main idea to solve this problem is to use Priority Queue.
2. Iterate in the array of linked lists and store all pairs {values, head pointers} in the min-heap.
3.  Each time, pop out the node with the minimum value from the min-heap and make it the next node of the newly formed linked list.
4. Also, check if the popped node has the next node, then insert the pair {value, next node} in the min-heap again.
5. Above mentioned process, results in the formation of a new linked list with all the values sorted in ascending order since every time, we’re extracting the node with minimum value and making it the next node of the new linked list.
6. Finally, we have merged k linked lists.

## Code

### Merge k Sorted Lists Leetcode C++ Solution:

```class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
if(lists.empty()){
return nullptr;
}
ListNode* dummy = new ListNode(0);
priority_queue<pair<int,ListNode*>,vector<pair<int,ListNode*>>,greater<pair<int,ListNode*>>> pq;
for(auto& node:lists){
if(node!=nullptr){
pq.push({node->val,node});
}
}
while(!pq.empty()){
ListNode* node = pq.top().second;
pq.pop();
if(node->next!=nullptr){
pq.push({node->next->val,node->next});
}
dummy->next = node;
dummy = node;
}
}
};```

### Merge k Sorted Lists Leetcode Java Solution:

```class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if(lists.length==0){
return null;
}
PriorityQueue<ListNode> pq = new PriorityQueue<ListNode>(lists.length, (a,b)-> a.val-b.val);
for(ListNode node:lists){
if(node!=null){
}
}
ListNode dummy = new ListNode(0);
while(!pq.isEmpty()){
ListNode node = pq.poll();
if(node.next!=null){
}
dummy.next = node;
dummy = node;
}
}
}```

## Complexity Analysis for Merge k Sorted Lists Leetcode Solution

### Time Complexity

The time complexity of the above code is O(NKlogK). Each node is pushed into the min-heap once and there are total at most N*K nodes in the given array of linked lists, where N = maximum number of nodes in a single linked list and K = size of the array of the linked list.

### Space Complexity

The space complexity of the above code is O(K) since we’re using a min-heap of maximum size k.