Reverse Nodes in k-Group
Problem
k nodes and reverse
the order of nodes inside each full block. A trailing block shorter than
k stays as it is. Rearrange the nodes themselves — changing only the
values is not allowed.[1,2,3,4,5], k=2Output[2,1,4,3,5][1,2,3,4,5], k=3Output[3,2,1,4,5]1 ≤ k ≤ n ≤ 5000 · 0 ≤ Node.val ≤ 1000 · Follow-up: O(1) extra memory.
Try it yourself
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
}
}
k-1 moves per group, all via a fixed
prev anchor.Instinct Nodes joined by next pointers and the task is to reverse, splice, merge, reorder or remove in place - grab a dummy head and rewire pointers carefully.
Memory hack Save next, flip, step - never let go of a rope before you've grabbed the next one.
Open the Linked List Techniques guide →Approaches
Brute ForceNode Array, Reverse Chunks, Relink
O(n)Space O(n)Copy all node references into an array. Reverse every full window
[i, i+k) of the array with two pointers, leave the tail window alone,
then rebuild the chain in array order. Nodes move, values don't.
public ListNode reverseKGroup(ListNode head, int k) { List<ListNode> nodes = new ArrayList<>(); for (ListNode c = head; c != null; c = c.next) nodes.add(c); int n = nodes.size(); for (int start = 0; start + k <= n; start += k) { for (int l = start, r = start + k - 1; l < r; l++, r--) { Collections.swap(nodes, l, r); } } for (int i = 0; i < n - 1; i++) nodes.get(i).next = nodes.get(i + 1); nodes.get(n - 1).next = null; return nodes.get(0); }
Simple and linear, but the array breaks the O(1)-memory follow-up.
BetterRecursion per Group
O(n)Space O(n/k)Probe k nodes ahead. If fewer exist, return head
unchanged. Otherwise recursively solve the list after the group first, then reverse the
current k nodes so the group's old head points at that solved remainder.
public ListNode reverseKGroup(ListNode head, int k) { ListNode cur = head; int count = 0; while (cur != null && count < k) { // find the (k+1)-th node cur = cur.next; count++; } if (count < k) return head; // short tail: leave as is cur = reverseKGroup(cur, k); // cur = head of the solved rest while (count-- > 0) { // prepend group nodes onto cur ListNode next = head.next; head.next = cur; cur = head; head = next; } return cur; }
Neat and in-place, but one stack frame per group.
OptimalIterative Head-Insertion with Dummy
O(n)Space O(1)Count nodes once. For each full group, prev sits before it and
curr is its first node (which ends up last). k-1 times, unlink
curr.next and insert it right after prev. Then
curr becomes the next group's prev.
public ListNode reverseKGroup(ListNode head, int k) { ListNode dummy = new ListNode(0, head), prev = dummy; int count = 0; for (ListNode c = head; c != null; c = c.next) count++; while (count >= k) { ListNode curr = prev.next, next = curr.next; for (int i = 1; i < k; i++) { curr.next = next.next; // unlink next next.next = prev.next; // put it at the group front prev.next = next; next = curr.next; } prev = curr; // old first node is now the group's tail count -= k; } return dummy.next; }
Dry runhead=[1,2,3,4,5], k=3
- group 1Dp1c2n345count=5 ≥ 3
- i=1Dp21c3n45move 2 after prev
- i=2Dp321c4n5move 3 after prev
- endD321p45prev=1, count=2 < 3 ✔
Each node handled O(1) times, constant memory — meets the follow-up.
At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Node Array, Reverse Chunks, Relink | O(n) | O(n) |
| Better | Recursion per Group | O(n) | O(n/k) |
| Optimal | Iterative Head-Insertion with Dummy | O(n) | O(1) |
- Reversing the last partial group — check that k nodes remain before reversing.
- Losing the link from the previous group's tail to the new group head.
- Forgetting a dummy node — the first group changes the list's head.
- Reduce to a known sub-problem: “reverse k nodes between two anchors”.
- Mention the recursive version first, then improve to O(1) space for the follow-up.
- Test k=1 (no change), k=n (full reverse) and n not divisible by k.