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
linked–lists lists
, each linked-list is sorted in ascending order.
Merge all the linked-lists into one sorted linked-list and return it.
Example 1:
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:
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 exceed104
.
Now, let’s 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 Lists Leetcode Solution in 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.