# Merge k Sorted Lists Leetcode Solution

In this post, we are going to solve the Merge k Sorted Lists Leetcode Solution problem of Leetcode. This Leetcode problem is done in many programming languages like C++, Java, and Python.

## Problem

You are given an array of `k` linkedlists `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`.

Now, lets see the leetcode solution of Merge k Sorted Lists Leetcode Solution.

### Merge k Sorted Lists Leetcode 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
```

### Merge k Sorted ListsLeetcode Solutionin CPP

```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 Lists Leetcode 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;
}
}
```

Note: This problem Merge k Sorted Lists is generated by Leetcode but the solution is provided by Chase2learn This tutorial is only for Educational and Learning purposes.

Sharing Is Caring