The trick here is to name the state correctly, then let the implementation follow. For 25. Reverse Nodes in k-Group, the solution in this repository is mainly a straightforward implementation solution.
Guide
What?
We want to turn the problem statement into a smaller set of decisions the computer can repeat safely. 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: straightforward implementation.
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 reverseTwoNodes, reverseKGroup, reverseOneGroup.
Guide
Why?
The solution works because it narrows the problem until every update has a clear reason to exist.
- 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(n) to O(n log n), depending on the dominant loop or data structure operation
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//Runtime: 20 ms, faster than 39.60% of C++ online submissions for Reverse Nodes in k-Group.
02//Memory Usage: 10.3 MB, less than 16.67% of C++ online submissions for Reverse Nodes in k-Group.
03/**
04 * Definition for singly-linked list.
05 * struct ListNode {
06 * int val;
07 * ListNode *next;
08 * ListNode() : val(0), next(nullptr) {}
09 * ListNode(int x) : val(x), next(nullptr) {}
10 * ListNode(int x, ListNode *next) : val(x), next(next) {}
11 * };
12 */
13class Solution {
14public:
15 void reverseTwoNodes(ListNode** a, ListNode** b){
16 //a and b are pointer of pointer
17 //a->x->... and b->y->... to b->a->x->... and y->...
18 // cout << "reverse: " << (*a)->val << " and " << (*b)->val << endl;
19 ListNode* latter = (*b)->next;
20 (*b)->next = *a;
21 //a->(b) and b->y->... to b->a->y->...
22 if((*a)->next == *b) (*a)->next = nullptr;
23 *a = *b;
24 *b = latter;
25 // cout << "reversed: " << ((*a) ? (*a)->val : -1) << " and " << ((*b) ? (*b)->val : -1) << endl;
26 };
27
28 ListNode* reverseKGroup(ListNode* head, int k) {
29 //check if the length of list >= k
30 ListNode* tail = head;
31 //go forward for k-1 steps
32 for(int i = 0; i < k-1 && tail; ++i){
33 tail = tail->next;
34 }
35 //the list's length < k, don't need to reverse it
36 if(!tail) return head;
37
38 //reverse the first k node and call function for rest nodes
39 ListNode* laterHead = reverseKGroup(tail->next, k);
40
41 // cout << "head: " << head->val << ", tail: " << tail->val << endl;
42 ListNode *cur = head, *next = head->next;
43 //each time reverse two nodes, reverse for k-1 times
44 for(int i = 0; i < k-1; ++i){
45 reverseTwoNodes(&cur, &next);
46 }
47
48 // cout << "new head: " << tail->val << ", new tail: " << head->val << endl;
49 // cout << "the reversed group: ";
50 // cur = tail;
51 // while(cur){
52 // cout << cur->val << " ";
53 // cur = cur->next;
54 // }
55 // cout << endl;
56
57 //original head of group now becomes the new tail
58 head->next = laterHead;
59 //tail is now the head of reversed list
60 return tail;
61 }
62};
63
64//recursion
65//https://leetcode.com/problems/reverse-nodes-in-k-group/discuss/11423/Short-but-recursive-Java-code-with-comments
66//Runtime: 24 ms, faster than 26.27% of C++ online submissions for Reverse Nodes in k-Group.
67//Memory Usage: 10.1 MB, less than 77.96% of C++ online submissions for Reverse Nodes in k-Group.
68//space: O(n/k) used by recursion stack
69/**
70 * Definition for singly-linked list.
71 * struct ListNode {
72 * int val;
73 * ListNode *next;
74 * ListNode() : val(0), next(nullptr) {}
75 * ListNode(int x) : val(x), next(nullptr) {}
76 * ListNode(int x, ListNode *next) : val(x), next(next) {}
77 * };
78 */
79class Solution {
80public:
81 ListNode* reverseKGroup(ListNode* head, int k) {
82 ListNode* cur = head;
83
84 int steps = 0;
85
86 for(; steps < k && cur; ++steps){
87 cur = cur->next;
88 }
89
90 //list's length < k, don't need to reverse
91 if(steps < k) return head;
92
93 //now cur is the head of next group, reverse that group first
94 cur = reverseKGroup(cur, k);
95
96 /*
97 123456, k = 3
98 assume the later group is already reversed: 123654
99 head: 1, cur: 6
100 "head" is the head of list to be reversed,
101 and it should be connected to the head of reversed list,
102 so we set head->next to "cur"
103 tmp: 2, head->next: 6,
104 and later do the following:
105 cur: 1, head: 2
106 so that cur is still the head of reversed list and
107 "head" is still the head of the list to be reversed
108
109 we do this for k times,
110 tmp: 3, head->next: 1, cur: 2, head: 3
111 tmp: nullptr, head->next: 2, cur: 3, head: nullptr
112
113 to summary, in each iteration,
114 we cut the head of forward list and append it to the head of reversed list,
115 and this process is done for k times,
116 meaning cutting for k times and appending for k times
117 */
118 for(int i = 0; i < k; ++i){
119 //"head": head of the list to be reversed
120 ListNode* tmp = head->next;
121 //cur: head of reversed list
122 head->next = cur;
123 cur = head;
124 head = tmp;
125 }
126
127 return cur;
128 }
129};
130
131//non-recursive
132//https://leetcode.com/problems/reverse-nodes-in-k-group/discuss/11440/Non-recursive-Java-solution-and-idea
133/**
134 * Definition for singly-linked list.
135 * struct ListNode {
136 * int val;
137 * ListNode *next;
138 * ListNode() : val(0), next(nullptr) {}
139 * ListNode(int x) : val(x), next(nullptr) {}
140 * ListNode(int x, ListNode *next) : val(x), next(next) {}
141 * };
142 */
143class Solution {
144public:
145 ListNode* reverseOneGroup(ListNode* head_prev, ListNode* tail_next){
146 //head_prev: the node before current group's head
147 //tail_prev: the node after current group's tail
148 /**
149 * Reverse a link list between begin and end exclusively
150 * an example:
151 * a linked list:
152 * 0->1->2->3->4->5->6
153 * | |
154 * begin end
155 * after call begin = reverse(begin, end)
156 *
157 * 0->3->2->1->4->5->6
158 * | |
159 * begin end
160 * @return the reversed list's 'begin' node,
161 which is the precedence of node end
162 */
163 ListNode* cur = head_prev->next;
164 ListNode* new_head_prev = cur;
165 ListNode* prev = head_prev;
166 ListNode* next;
167 /*
168 0->1->2->3->4, begin: 0, end: 4, cur: 1
169 1->0
170 2->1->0
171 3->2->1->0
172 prev: the previous node of cur
173 next: the next node of cur
174 */
175 while(cur != tail_next){
176 next = cur->next;
177 cur->next = prev;
178 prev = cur;
179 cur = next;
180 }
181
182 /*
183 now:
184 prev: 3, cur: 4
185 */
186 head_prev->next = prev;
187 new_head_prev->next = cur;
188
189 return new_head_prev;
190 };
191
192 ListNode* reverseKGroup(ListNode* head, int k) {
193 if(!head || !head->next || k == 1) return head;
194
195 ListNode* dummy_head = new ListNode(-1);
196 dummy_head->next = head;
197 ListNode* group_head_prev = dummy_head;
198
199 for(int i = 1; head; ++i){
200 if(i%k == 0){
201 /*
202 for 12345, k = 3,
203 it will reverse the first group when head points to 3,
204 at that time,
205 group_head_prev is 0, head->next is 4
206 */
207 group_head_prev = reverseOneGroup(group_head_prev, head->next);
208 head = group_head_prev->next;
209 }else{
210 head = head->next;
211 }
212 }
213
214 return dummy_head->next;
215 }
216};Cost
Complexity
Time
O(n) to O(n log n), depending on the dominant loop or data structure operation
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(n) in the usual case for auxiliary containers or recursion
Auxiliary state plus the answer structure where the problem requires one.