A complete visual walkthrough of iterative k-group linked list reversal — from brute force to optimal O(1) space.
The simplest approach: copy all node values into an array, reverse every consecutive group of k values in the array, then rebuild the linked list from the modified array.
First 3 values are reversed. The last 2 values (less than k) remain in their original order. Then rebuild a new linked list from this array.
This works but uses O(n) extra space for the array. The problem specifically asks: "Can you solve the problem in O(1) extra memory space?" We need to reverse the links in-place.
The real challenge: Reversing a section of a linked list is straightforward. The tricky part is reconnecting each reversed group to the previous group and the next group without losing any references.
We process the list in groups of k nodes. For each group, we perform four sub-steps:
null before k steps, stop — the remaining nodes stay as-is.next to the previous node.groupPrev to the end of the just-reversed group (the old first node). Repeat.Why a dummy head? The first group has no "previous node." A dummy node before the head gives us a uniform groupPrev pointer for every group, including the first one. This eliminates special-case handling.
Notice how prev now points to node 3 (the new head of the group), and node 1 (the old head, now the tail) points to next (the start of the unreversed portion). The groupPrev pointer then advances to node 1.
Let's trace through [1, 2, 3, 4, 5] with k = 3 step by step.
We create a dummy node pointing to the head. groupPrev starts at the dummy.
Starting from groupPrev (dummy), walk 3 steps: dummy→1→2→3. We reach node 3, so kth = 3. Three nodes remain — proceed with reversal.
Reverse the pointers within the group. prev starts as groupNext (node 4), so node 1 will point to node 4 after reversal.
Set groupPrev.next = kth (dummy→3) and advance groupPrev to the old first node (node 1, now at the tail of the reversed group).
Starting from groupPrev (node 1), walk 3 steps: 1→4→5→null. We hit null before completing 3 steps, so kth = null. Only 2 nodes remain — not enough for a full group.
These are the scenarios you should keep in mind when implementing or testing:
getKth check fails immediately — no reversal happens. The list is returned as-is.
Constraint reminder: The problem guarantees 1 ≤ k ≤ n, so k > n won't appear in LeetCode test cases. But a robust implementation handles it anyway — and ours does, for free.
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int val, ListNode next) { * this.val = val; this.next = next; * } * } */ class Solution { public ListNode reverseKGroup(ListNode head, int k) { // Dummy node simplifies head-of-list edge case ListNode dummy = new ListNode(0, head); ListNode groupPrev = dummy; while (true) { // 1. Find the k-th node from groupPrev ListNode kth = getKth(groupPrev, k); if (kth == null) break; // fewer than k nodes left // 2. Save the node after this group ListNode groupNext = kth.next; // 3. Reverse the k nodes in this group // prev starts at groupNext so the last reversed // node points to the rest of the list ListNode prev = groupNext; ListNode curr = groupPrev.next; while (curr != groupNext) { ListNode next = curr.next; // save next curr.next = prev; // reverse pointer prev = curr; // advance prev curr = next; // advance curr } // 4. Reconnect: the old first node is now the tail ListNode tmp = groupPrev.next; // old first (now tail) groupPrev.next = kth; // point to new head (kth) groupPrev = tmp; // advance to tail for next iteration } return dummy.next; } // Walk k steps from node; return null if fewer than k nodes remain private ListNode getKth(ListNode node, int k) { while (node != null && k > 0) { node = node.next; k--; } return node; } }
Key detail in the reversal loop: Notice prev starts as groupNext, not null. This is what seamlessly connects the tail of the reversed group to the rest of the list. Without this, node 1 would point to null instead of node 4, breaking the chain.
Enter a list and a value for k, then step through the algorithm to see each group identified and reversed in real time.
Each node is visited at most twice: once during the getKth check and once during reversal. The total work across all groups is O(n). We use only a constant number of pointers — no arrays, stacks, or recursion.
Compared to brute force: The brute force approach also runs in O(n) time but requires O(n) extra space for the value array. Our in-place solution achieves the same time complexity with O(1) space — exactly what the problem asks for.