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 int val;
3 ListNode next;
4 ListNode(int x) { val = x; }
5}
6
7public class Solution {
8 public ListNode reverseKGroup(ListNode head, int k) {
9 if (head == null || k == 1) return head;
10 ListNode dummy = new ListNode(0);
11 dummy.next = head;
12 ListNode prev = dummy, current = head;
13
14 int len = 0;
15 while (current != null) {
16 len++;
17 current = current.next;
18 }
19
20 current = dummy.next;
21 while (len >= k) {
22 current = prev.next;
23 ListNode next = current.next;
24 for (int i = 1; i < k; ++i) {
25 current.next = next.next;
26 next.next = prev.next;
27 prev.next = next;
28 next = current.next;
29 }
30 prev = current;
31 len -= k;
32 }
33 return dummy.next;
34 }
35}
36A dummy node initializes and tracks the head of the modified list. The length of the linked list is found to determine feasibility of group operations. If viable, node pointers are adjusted to reverse nodes within each complete 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 function probes node groups, inspecting k node availability. Featuring recursive return principles, node alignment reverses within recursive function sweeps which link completed segments reverting at recursion levels until resolution.