Reverse Nodes in k-Group

Problem in Plain English

Given the head of a linked list and an integer k, reverse the nodes k at a time, leaving fewer than k trailing nodes as they are, using only pointer changes.

Problem Statement

Given the head of a linked list, reverse its nodes k at a time and return the modified list.

If fewer than k nodes remain at the end, leave them as they are. Only node links may change, never node values.

Constraints

The number of nodes in the list is $n$ .
$1 \le k \le n \le 5000$ .
$0 \le \mathrm{Node.val} \le 1000$ .
Only change links between the existing nodes; do not change their values.

Examples

Example 1

Input: head = [1,2,3,4,5], k = 2
Output: [2,1,4,3,5]

Reverse the complete pairs of original nodes [1,2] and [3,4]. The final node 5 cannot form a pair, so its next link remains null.

Example 2

Input: head = [1,2,3,4,5], k = 3
Output: [3,2,1,4,5]

Reverse the first complete group of three. The trailing nodes 4 and 5 form a short group: keep 4 -> 5 -> null unchanged and connect the new tail 1 to node 4.

Example 3

Input: head = [7], k = 1
Output: [7]

A one-node group is already reversed. Return the same node with its value and null next link unchanged.

Example 4

Input: head = [1,2,3,4], k = 4
Output: [4,3,2,1]

The entire list is one complete group. The original head 1 becomes the last node and must point to null.

Intuition

A full group can be reversed by changing its links, but its original first node becomes its new tail. In Example 1, reversing nodes 1 and 2 creates 2 -> 1; node 1 must then connect to the next reversed group, 4 -> 3. Keep the boundary after each group before rewiring anything. If the suffix has fewer than k nodes, keep every link in that suffix unchanged. Node identity matters: swapping values would produce the same numbers but violate the requirement.

Approaches

Recursive Groups

Solution Details

Reveal Recursive Groups: intuition, complexity, and code

Intuition

Reverse one complete group, then let a recursive call solve the remaining suffix and attach its answer to the old group head, now the tail. First walk k links without mutation to prove that a full group exists. For Example 1, calls starting at nodes 1 and 3 reverse the pairs, while the call starting at node 5 returns that short suffix untouched. The recursion stack remembers which group tails still need their suffix answers.

Step-by-Step Logic

Return immediately for an empty list or k equal to 1. Otherwise solve groups recursively; the Python wrapper first counts nodes to reserve enough recursion capacity for the supported input bound.
Starting at the current group head, walk k links before changing any pointer. In Example 1, the call at node 1 walks through nodes 1 and 2, leaving the boundary pointer on node 3. If this walk reaches null too soon, return the original group head unchanged.
Set prev to null and node to the group head. Repeat k times: save node.next, redirect node.next to prev, then advance prev and node. The first pair becomes 2 -> 1 -> null, with prev at 2 and node at 3.
Recursively solve the suffix starting at node. The call at node 3 similarly reverses 3 and 4, then the call at node 5 returns 5 because it cannot find a second node.
On each return, connect the old head to the returned suffix head. Node 3 links to 5, then node 1 links to 4. Return prev from the first call, node 2, giving [2,1,4,3,5].

Why It Works

Use induction on the number of complete groups in a suffix. If fewer than k nodes remain, the size check makes no mutations and returns exactly the required unchanged suffix. Otherwise the reversal loop maintains prev as the reversed portion of this group and node as the first unprocessed node; saving the next link keeps every node reachable through these anchors. After k iterations, prev is the new group head and the old head is its null-terminated tail. By induction the recursive call returns the correctly arranged suffix. Connecting the old head to that result joins the two disjoint node sets without duplicating, losing or changing any node value. Returning prev therefore produces precisely the required group reversal.

Dry Run

Recursive Groups: variable states at each step
Event / call head	Boundary check	prev after event	node after event	Changed link / result
Call at 1: check	1 -> 2 -> 3; full group	null	1	No links changed
Call at 1: reverse 1	suffix begins at 3	1	2	1.next: 2 -> null; save next = 2
Call at 1: reverse 2	suffix begins at 3	2	3	2.next: 3 -> 1; save next = 3; group 2 -> 1 -> null
Call at 3: check	3 -> 4 -> 5; full group	null	3	Call at 1 waits with prev = 2 and old head = 1
Call at 3: reverse 3	suffix begins at 5	3	4	3.next: 4 -> null; save next = 4
Call at 3: reverse 4	suffix begins at 5	4	5	4.next: 5 -> 3; save next = 5; group 4 -> 3 -> null
Call at 5: check	5 -> null, then missing second node	not initialized	not initialized	Return 5; 5.next remains null
Return from call at 3	suffix result = 5	4	5	Set 3.next = 5; return 4 -> 3 -> 5
Return from call at 1	suffix result = 4	2	3	Set 1.next = 4; return [2,1,4,3,5]

Complexity Analysis

Time Complexity

O(n)

Space Complexity

O(n/k)

For k greater than 1, each complete group is checked and reversed once, and the final short suffix is checked once. Python also makes one initial counting pass. There are floor(n/k) complete-group frames plus a terminating call, so stack space is O(n/k) for valid k <= n. No replacement list nodes are allocated; the existing nodes are the output. When k is 1, the early return takes O(1) time and space. Python temporarily raises and then restores the interpreter recursion limit to support the stated bounds; the iterative approach avoids the stack entirely.

Code

Solution.java

1class ListNode {2    int val;3    ListNode next;4    ListNode(int val) { this.val = val; }5    ListNode(int val, ListNode next) { this.val = val; this.next = next; }6}7
8class Solution {9    public ListNode reverseKGroup(ListNode head, int k) {10        if (head == null || k == 1) return head;11        // Check the entire group before mutating; a short suffix stays untouched.12        ListNode boundary = head;13        for (int i = 0; i < k; i++) {14            if (boundary == null) return head;15            boundary = boundary.next;16        }17        ListNode prev = null;18        ListNode node = head;19        for (int i = 0; i < k; i++) {20            // Save the unreversed suffix before redirecting this link.21            ListNode next = node.next;22            node.next = prev;23            prev = node;24            node = next;25        }26        // The original head is now the tail; attach the recursively solved suffix.27        head.next = reverseKGroup(node, k);28        return prev;29    }30}

Hints

Hint 1

A short final group must keep all its original links. How can you prove the next group has k nodes before changing anything?

Hint 2

Reversing k nodes makes the original group head its new tail. Save both that node and the pointer to the next group.

Hint 3

Use either a recursive suffix answer or a dummy node and previous-group tail to reconnect the two boundaries after each reversal.

Edge Cases

When k is 1, return the same head and keep every node and link unchanged.
When k equals n, reverse the entire list and ensure the original head now points to null.
If n is a multiple of k, every group reverses; otherwise the final n modulo k nodes retain all their original next links.
Equal values can hide a wrong answer: even [8,8] with k = 2 must reverse the two node identities.
At n = 5000 and k = 2, recursion has about 2500 group frames. The Python wrapper reserves capacity; prefer the iterative version when constant space is required.

Common Mistakes and Interview Tips

Reversing until null without first checking group size incorrectly changes a short trailing group.
Redirecting a next link before saving it loses the unreversed suffix.
Treating the old group head as the new head: it is the new tail and must connect to the next suffix.
Advancing prevGroupTail to the new group head instead of the new tail splices the next group into the previous group.
Swapping node values or allocating replacement output nodes hides an identity violation even when the displayed values match.
Claiming constant space for recursion ignores the waiting group frames; without a k = 1 early return, even unchanged single-node groups unnecessarily deepen recursion.

Key Takeaway

For group operations on a linked list, first prove that the group is complete, then preserve its outside boundary before rewiring. The old head becomes the reversed group tail, so reconnect both ends and advance from that tail. A dummy node makes the first group follow the same rules as later groups; recursion instead stores the pending tail connections on its stack.