Last updated on January 20th, 2025 at 10:58 pm
Here, we see a Merge k Sorted Lists LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Divide and Conquer, Heap, Linked List
Companies
Adobe, Airbnb, Facebook, Google, LinkedIn, Microsoft, Twitter, Uber
Level of Question
Hard

Merge k Sorted Lists LeetCode Solution
Table of Contents
1. 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.
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: []
2. Coding Pattern Used in Solution
The provided code follows the K-way Merge pattern. This pattern is commonly used to merge multiple sorted arrays or linked lists into a single sorted array or linked list. The key idea is to repeatedly merge smaller subsets of the input until the entire input is merged into one sorted output.
3. Code Implementation in Different Languages
3.1 Merge k Sorted Lists C++
class Solution { public: ListNode* mergeKLists(vector<ListNode*>& lists) { priority_queue<ListNode*, vector<ListNode*>, compare> q; for (auto l : lists) { if (l) { q.push(l); } } ListNode pre(0); ListNode *node = ⪯ while (q.size()) { ListNode *top = q.top(); q.pop(); node->next = top; node = node->next; if (top->next) { q.push(top->next); } } return pre.next; } struct compare { bool operator()(const ListNode* l1, const ListNode* l2) { return l1->val > l2->val; } }; };
3.2 Merge k Sorted Lists Java
class Solution { public ListNode mergeKLists(ListNode[] lists) { return partion(lists,0,lists.length-1); } public static ListNode partion(ListNode[] lists,int s,int e){ if(s==e) return lists[s]; if(s<e){ int q=(s+e)/2; ListNode l1=partion(lists,s,q); ListNode l2=partion(lists,q+1,e); return merge(l1,l2); }else return null; } public static ListNode merge(ListNode l1,ListNode l2){ if(l1==null) return l2; if(l2==null) return l1; if(l1.val<l2.val){ l1.next=merge(l1.next,l2); return l1; }else{ l2.next=merge(l1,l2.next); return l2; } } }
3.3 Merge k Sorted Lists JavaScript
function mergeLists(a, b) { const dummy = new ListNode(0); let temp = dummy; while (a !== null && b !== null) { if (a.val < b.val) { temp.next = a; a = a.next; } else { temp.next = b; b = b.next; } temp = temp.next; } if (a !== null) { temp.next = a; } if (b !== null) { temp.next = b; } return dummy.next; } var mergeKLists = function(lists) { if (lists.length === 0 ) { return null; } while (lists.length > 1) { let a = lists.shift(); let b = lists.shift(); const h = mergeLists(a, b); lists.push(h); } return lists[0]; };
3.4 Merge k Sorted Lists Python
class Solution(object): def mergeKLists(self, lists): if not lists: return None if len(lists) == 1: return lists[0] mid = len(lists) // 2 l, r = self.mergeKLists(lists[:mid]), self.mergeKLists(lists[mid:]) return self.merge(l, r) def merge(self, l, r): dummy = p = ListNode() while l and r: if l.val < r.val: p.next = l l = l.next else: p.next = r r = r.next p = p.next p.next = l or r return dummy.next def merge1(self, l, r): if not l or not r: return l or r if l.val< r.val: l.next = self.merge(l.next, r) return l r.next = self.merge(l, r.next) return r
4. Time and Space Complexity
Time Complexity | Space Complexity | |
C++ | O(n log k) | O(k) |
Java | O(n log k) | O(log k) |
JavaScript | O(n log k) | O(1) |
Python | O(n log k) | O(log k) |
where,
n is the total number of nodes across all lists.
k is the number of lists.
- Time Complexity:
- The time complexity is dominated by the merging process.
- For all implementations, the total number of nodes processed is (N), and the merging process involves (O(\log K)) levels (either due to the heap or divide-and-conquer).
- Space Complexity:
- C++ uses a heap, so the space complexity is (O(K)).
- Java and Python use recursion, so the space complexity is (O(\log K)) due to the recursion stack.
- JavaScript uses an iterative approach, so the space complexity is (O(1)).