#25 Reverse Nodes in k-Group
the problem
In plain words
Given the head of a linked list and an integer k, reverse the nodes k at a time and return the new head. If fewer than k nodes are left at the end, leave them in their original order. Only the links may change, not the values.
in head = [1,2,3,4,5], k = 2
out [2,1,4,3,5]
in head = [1,2,3,4,5], k = 3
out [3,2,1,4,5]
- 1 ≤ k ≤ n ≤ 5000
- 0 ≤ Node.val ≤ 1000
- Follow-up: O(1) extra memory
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternIn-place linked-list rewiring
It's LC 206 run on one block at a time. Before each block, check that k nodes exist; reverse exactly those k, starting prev at the node after the block; then hook the previous block's tail to the new block head. groupPrev (a dummy at first) is that hook.
solutions
From brute force to optimal
Put the nodes in an ArrayList, reverse each full block of k inside the array, then rewrite every next.
- Collect the nodes.
- For each full block: Collections.reverse(nodes.subList(s, s + k)).
- Relink in array order; the last node gets null.
One pass to collect, one to reverse blocks, one to relink.
The array of node references.
class Solution { public ListNode reverseKGroup(ListNode head, int k) { List<ListNode> nodes = new ArrayList<>(); for (ListNode p = head; p != null; p = p.next) nodes.add(p); for (int start = 0; start + k <= nodes.size(); start += k) { Collections.reverse(nodes.subList(start, start + k)); // only full groups } for (int i = 0; i + 1 < nodes.size(); i++) nodes.get(i).next = nodes.get(i + 1); nodes.get(nodes.size() - 1).next = null; return nodes.get(0); }}If k nodes exist, reverse the rest recursively first, then reverse this block onto it.
- Check k nodes exist; if not, return head.
- rest = reverseKGroup(node after the block, k).
- Reverse this block with prev = rest.
- Return the block's new head.
Each node is checked once and flipped once.
One stack frame per block — n frames when k = 1.
class Solution { public ListNode reverseKGroup(ListNode head, int k) { ListNode check = head; for (int i = 0; i < k; i++) { if (check == null) return head; // fewer than k nodes: leave them as they are check = check.next; } ListNode prev = reverseKGroup(check, k); // the rest, already done ListNode curr = head; for (int i = 0; i < k; i++) { // reverse this group onto it ListNode next = curr.next; curr.next = prev; prev = curr; curr = next; } return prev; // the group's old last node is its new head }}From groupPrev, find the k-th node. Reverse the block with prev = kth.next. Then groupPrev.next = kth, and groupPrev moves to the block's old first node.
- dummy → head; groupPrev = dummy.
- kth = k steps from groupPrev; if it doesn't exist, stop.
- Reverse groupPrev.next … kth with prev = kth.next.
- oldFirst = groupPrev.next; groupPrev.next = kth; groupPrev = oldFirst. Repeat.
Each node is visited twice: once while finding the k-th node, once while flipping.
A fixed number of references, whatever n and k are.
class Solution { public ListNode reverseKGroup(ListNode head, int k) { ListNode dummy = new ListNode(0, head); ListNode groupPrev = dummy; // the node just before the next group while (true) { ListNode kth = groupPrev; for (int i = 0; i < k && kth != null; i++) kth = kth.next; if (kth == null) break; // fewer than k nodes left: keep them as they are ListNode groupNext = kth.next; // first node after this group ListNode prev = groupNext, curr = groupPrev.next; while (curr != groupNext) { ListNode next = curr.next; curr.next = prev; prev = curr; curr = next; } ListNode oldFirst = groupPrev.next; // now the group's last node groupPrev.next = kth; // the old k-th node is the group's new head groupPrev = oldFirst; } return dummy.next; }}Dry run
in the room
How to say it in the interview
talk track
- Split it out loud into two helpers: "find the k-th node from here" and "reverse one block". Interviewers grade the decomposition.
- Explain why
prevstarts at groupNext: the block's first node must end up pointing at the next block. - After a block, the old first node is the block's tail — it becomes the next
groupPrev. - Mention the recursive version's O(n/k) stack, then give the O(1) loop.
traps
- Reversing a short last block — check that k nodes exist before touching anything.
- Starting
prevat null: the block's new tail then points to null and the rest of the list is cut off. - Forgetting to move
groupPrevto the block's old first node.
what they ask next
Follow-ups
What if the short last block must be reversed too?
Drop the "k nodes exist?" check and reverse min(k, remaining) nodes each time.
How does Swap Nodes in Pairs relate?
It is exactly this problem with k = 2.
before you submit
Edge cases to test
- k = 1 → the list is unchanged.
- k = n → the whole list is reversed once.
- n not a multiple of k → the short last block stays in order.
- n a multiple of k → every block flips.
practise next
Similar problems
- #92Reverse Linked List IIMediumin Linked Lists
- #206Reverse Linked ListEasyin Linked Lists
- #24Swap Nodes in PairsMediumin Recursion