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.
1class ListNode:
2 def __init__(self, val=0, next=None):
3 self.val = val
4 self.next = next
5
6class Solution:
7 def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
8 if not head or k == 1:
9 return head
10
11 dummy = ListNode(0)
12 dummy.next = head
13 prev, current = dummy, head
14
15 length = 0
16 while current:
17 length += 1
18 current = current.next
19
20 while length >= k:
21 current = prev.next
22 next = current.next
23 for i in range(1, k):
24 current.next = next.next
25 next.next = prev.next
26 prev.next = next
27 next = current.next
28 prev = current
29 length -= k
30
31 return dummy.next
32The solution constructs a dummy node linked to the head, simplifying edge operations. Counting list length allows determination of how many full k-reversals are possible. Nodes in these groups are then reversed using iterative swaps of pointers.
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
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {}
};
class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
if (!head) return nullptr;
ListNode* current = head;
int count = 0;
while (current && count < k) {
current = current->next;
count++;
}
if (count == k) {
current = reverseKGroup(current, k);
while (count--) {
ListNode* temp = head->next;
head->next = current;
current = head;
head = temp;
}
head = current;
}
return head;
}
};
Similar principle of recursion is applied. The function reverses a complete k-group comparing recursively returned segments. Adjust head/next pointers in each call level utilizing recursive reforming of node links.