# Merge K Sorted List Program Solution

We at gradjobopenings.com provide free job alerts of freshers job drives. In this website we list on campus job openings for freshers and off campus job openings for freshers and also work from home job openings. This is the best website to apply for off campus drive in India. Visit our website for government job alerts and private job alerts. We also list free interview notes and study materials, one of the best interview study website.comfortable to face the interviews:

You are given an array of `k` linked-lists `lists`, each linked-list is sorted in ascending order.

Example 1:

```Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
[
1->4->5,
1->3->4,
2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6
```

Example 2:

```Input: lists = []
Output: []
```

Example 3:

```Input: lists = [[]]
Output: []
```

Constraints:

• `k == lists.length`
• `0 <= k <= 104`
• `0 <= lists[i].length <= 500`
• `-104 <= lists[i][j] <= 104`
• `lists[i]` is sorted in ascending order.
• The sum of `lists[i].length` will not exceed `104`.
• Time: O(n\log k)O(nlogk)
• Space: O(k)O(k)

### Merge K Sorted List Program Solution In C++

``````class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
ListNode dummy(0);
ListNode* curr = &dummy;
auto compare = [](ListNode* a, ListNode* b) { return a->val > b->val; };
priority_queue<ListNode*, vector<ListNode*>, decltype(compare)> minHeap(
compare);

for (ListNode* list : lists)
if (list)
minHeap.push(list);

while (!minHeap.empty()) {
ListNode* minNode = minHeap.top();
minHeap.pop();
if (minNode->next)
minHeap.push(minNode->next);
curr->next = minNode;
curr = curr->next;
}

return dummy.next;
}
};
``````

### Merge K Sorted List Program Solution In JAVA

``````class Solution {
public ListNode mergeKLists(ListNode[] lists) {
ListNode dummy = new ListNode(0);
ListNode curr = dummy;
Queue<ListNode> minHeap = new PriorityQueue<>((a, b) -> a.val - b.val);

for (final ListNode list : lists)
if (list != null)
minHeap.offer(list);

while (!minHeap.isEmpty()) {
ListNode minNode = minHeap.poll();
if (minNode.next != null)
minHeap.offer(minNode.next);
curr.next = minNode;
curr = curr.next;
}

return dummy.next;
}
}
``````

### Merge K Sorted List Program Solution In Python

``````from queue import PriorityQueue

class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
dummy = ListNode(0)
curr = dummy
pq = PriorityQueue()

for i, lst in enumerate(lists):
if lst:
pq.put((lst.val, i, lst))

while not pq.empty():
_, i, minNode = pq.get()
if minNode.next:
pq.put((minNode.next.val, i, minNode.next))
curr.next = minNode
curr = curr.next

return dummy.next
``````
error: Content is protected !!