A good way into this one is to ask: what do we need to remember so we never redo work blindly? For 23. Merge k Sorted Lists, the solution in this repository is mainly a heap / priority queue solution.
Guide
What?
The first job is to translate the English prompt into state, transition, and stopping conditions. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: heap / priority queue.
The notes already sitting in the source point us in the right direction:
- Approach 1: Brute Force
- time: O(NlogN), collect all nodes and then sort
- space: O(N)
- Approach 2: Compare the head of linked list
Guide
When?
This pattern shows up when the brute force version has too many repeated checks, too many possible branches, or too much bookkeeping to do by hand. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are mergeKLists, mergeTwoLists.
Guide
Why?
The win comes from making each line carry responsibility: store the useful state, discard the rest, keep moving.
- The queue gives the solution a level-by-level or frontier-style traversal.
- The heap keeps the best candidate available without sorting the whole world every time.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Read the setup variables first.
- Follow the main loop or recursive helper next.
- Watch where invalid states get skipped.
- Check which value survives to the return statement.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(KN), space: O(1)
- Space: O(K) for the priority queue
Guide
C++ Solution
Your submission
The accepted solution
01//Approach 1: Brute Force
02//time: O(NlogN), collect all nodes and then sort
03//space: O(N)
04
05//Approach 2: Compare the head of linked list
06//time: O(KN), k: #linked list
07//space: O(N) -> O(1) if in-place
08
09//Approach 3: Optimize Approach 2 by Priority Queue
10//Runtime: 36 ms, faster than 64.12% of C++ online submissions for Merge k Sorted Lists.
11//Memory Usage: 12 MB, less than 71.35% of C++ online submissions for Merge k Sorted Lists.
12//time: O(NlogK)
13//space: O(K) for the priority queue
14/**
15 * Definition for singly-linked list.
16 * struct ListNode {
17 * int val;
18 * ListNode *next;
19 * ListNode() : val(0), next(nullptr) {}
20 * ListNode(int x) : val(x), next(nullptr) {}
21 * ListNode(int x, ListNode *next) : val(x), next(next) {}
22 * };
23 */
24class Solution {
25public:
26 ListNode* mergeKLists(vector<ListNode*>& lists) {
27 auto comp = [](const ListNode* a, const ListNode* b){
28 return a->val > b->val;
29 };
30 priority_queue<ListNode*, vector<ListNode*>, decltype(comp)> pq(comp);
31
32 for(ListNode* node : lists){
33 if(node != nullptr) pq.push(node);
34 }
35
36 ListNode* head = new ListNode(-1);
37 ListNode* cur = head;
38
39 while(!pq.empty()){
40 ListNode* node = pq.top(); pq.pop();
41 cur->next = node;
42 node = node->next;
43 cur = cur->next;
44 cur->next = nullptr;
45 if(node != nullptr){
46 pq.push(node);
47 }
48 }
49
50 return head->next;
51 }
52};
53
54//Approach 4: Merge lists one by one
55//extended from "21. Merge Two Sorted Lists"
56//Runtime: 248 ms, faster than 14.96% of C++ online submissions for Merge k Sorted Lists.
57//Memory Usage: 12.1 MB, less than 61.91% of C++ online submissions for Merge k Sorted Lists.
58//time: O(KN), space: O(1)
59class Solution {
60public:
61 ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
62 if(l1 == nullptr) return l2;
63 if(l2 == nullptr) return l1;
64 if(l1->val <= l2->val){
65 l1->next = mergeTwoLists(l1->next, l2);
66 return l1;
67 }else{
68 l2->next = mergeTwoLists(l2->next, l1);
69 return l2;
70 }
71 };
72
73 ListNode* mergeKLists(vector<ListNode*>& lists) {
74 ListNode *head = nullptr;
75
76 for(int i = 0; i < lists.size(); ++i){
77 head = mergeTwoLists(head, lists[i]);
78 }
79
80 return head;
81 }
82};
83
84//Approach 5: Merge with Divide And Conquer
85//Runtime: 16 ms, faster than 99.77% of C++ online submissions for Merge k Sorted Lists.
86//Memory Usage: 12.3 MB, less than 40.56% of C++ online submissions for Merge k Sorted Lists.
87//time: O(NlogK), space: O(1)
88class Solution {
89public:
90 ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
91 if(l1 == nullptr) return l2;
92 if(l2 == nullptr) return l1;
93 if(l1->val <= l2->val){
94 l1->next = mergeTwoLists(l1->next, l2);
95 return l1;
96 }else{
97 l2->next = mergeTwoLists(l2->next, l1);
98 return l2;
99 }
100 };
101
102 ListNode* mergeKLists(vector<ListNode*>& lists) {
103 int n = lists.size();
104 if(n == 0) return nullptr;
105
106 int interval = 1;
107
108 /*
109 divide and conquer
110 l0, l1, l2, l3, l4, l5
111 -> new l0(l0+l1), new l2(l2+l3), new l4(l4+l5)
112 -> new l0(l0+l2), l4
113 -> new l0(l0+l4)
114 */
115 while(interval < n){
116 for(int i = 0; i+interval < n; i += interval*2){
117 lists[i] = mergeTwoLists(lists[i], lists[i+interval]);
118 }
119 interval *= 2;
120 }
121
122 return lists[0];
123 }
124};Cost