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 <stdio.h>
2#include <stdlib.h>
3
4struct ListNode {
5 int val;
6 struct ListNode *next;
7};
8
9struct ListNode* reverseKGroup(struct ListNode* head, int k) {
10 if (!head || k == 1) return head;
11 struct ListNode dummy = {0, head};
12 struct ListNode *prev = &dummy, *current = head;
13
14 int len = 0;
15 while (current) {
16 len++;
17 current = current->next;
18 }
19
20 while (len >= k) {
21 current = prev->next;
22 struct ListNode *next = current->next;
23 for (int i = 1; i < k; i++) {
24 current->next = next->next;
25 next->next = prev->next;
26 prev->next = next;
27 next = current->next;
28 }
29 prev = current;
30 len -= k;
31 }
32 return dummy.next;
33}
34We count length of the list to check if a full k group exists. A dummy node facilitates manipulation of edge connections. For each complete k-length, we perform a series of node swaps. We adjust prev, current, and next pointers accordingly to achieve the reversal.
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
This recursive function inclusively reverses k nodes using a helper function and connects subsequent recursions via the next pointer. The recursion unwinds back, each time ending with any remaining nodes less than k in original order.