Sponsored
Sponsored
Use an iterative approach to reverse each group of k nodes separately. This approach leverages an auxiliary dummy node and previous and current pointers to manage the connections at each step. We traverse the list, checking for complete sets of k nodes to reverse them. If a group of nodes has less than k nodes, leave them as they are.
Time Complexity: O(n), where n is the number of nodes in the list, as each node is processed once.
Space Complexity: O(1), since no extra space is used apart from pointers.
1#include <iostream>
2
3struct ListNode {
4 int val;
5 ListNode* next;
6 ListNode(int x) : val(x), next(nullptr) {}
7};
8
9class Solution {
10public:
11 ListNode* reverseKGroup(ListNode* head, int k) {
12 if (!head || k == 1) return head;
13 ListNode dummy(0);
14 dummy.next = head;
15 ListNode* prev = &dummy;
16 ListNode* current = head;
17
18 int len = 0;
19 while (current) {
20 len++;
21 current = current->next;
22 }
23
24 while (len >= k) {
25 current = prev->next;
26 ListNode* next = current->next;
27 for (int i = 1; i < k; ++i) {
28 current->next = next->next;
29 next->next = prev->next;
30 prev->next = next;
31 next = current->next;
32 }
33 prev = current;
34 len -= k;
35 }
36 return dummy.next;
37 }
38};
39This implementation uses a similar approach to the C solution. A dummy node is initiated to ease node relinking operations. We loop through the list, checking if sufficient nodes remain to perform a k-group reversal, and adjust node pointers to reverse each k-group.
Recurse through the linked list, reversing k nodes at a time. If a full group of k nodes is found, reverse and connect through recursive calls. Terminate when fewer than k nodes are left. This approach inherently uses the call stack for management of reverse sequences.
Time Complexity: O(n), since we process each node once even recursively.
Space Complexity: O(n/k), the recursion depth in worst case equals the number of complete k-sized groups.
1
The Java recursive method determines when a k-group is fully completed. For these groups, node reversal is conducted, then rejoining occurs via recursive return proposing iterations terminated by incomplete k-arrangements.