LeetCode 25 - Reverse Nodes in k-Group

LeetCode Problem 25

Difficulty: 🔴 Hard
Topics: Linked List, Recursion

Solution

Problem Understanding

This problem asks us to reverse a singly linked list in groups of size k. Instead of reversing the entire list at once, we only reverse consecutive chunks containing exactly k nodes.

For example, if the linked list is:

1 -> 2 -> 3 -> 4 -> 5

and k = 2, we reverse every group of two nodes:

(1 -> 2) becomes (2 -> 1)
(3 -> 4) becomes (4 -> 3)

The final result is:

2 -> 1 -> 4 -> 3 -> 5

The last node remains unchanged because there are not enough nodes to form another full group of size 2.

The important detail is that we are not allowed to modify node values. We must physically rearrange the node pointers themselves. This means we cannot simply copy values into arrays and rewrite them. The linked structure must be manipulated directly.

The input consists of:

• head, the first node of a singly linked list
• k, the size of each reversal group

The output should be the head of the modified linked list after all valid groups have been reversed.

The constraints are:

• 1 <= k <= n <= 5000
• The linked list contains at most 5000 nodes

These constraints are small enough that even an O(n) or O(n log n) solution is acceptable, but the follow-up specifically asks whether we can achieve O(1) extra memory. That strongly suggests an in-place linked list manipulation solution.

Several edge cases are important:

• If k = 1, no reversal should happen.
• If the list length is smaller than k, the entire list remains unchanged.
• If the final group contains fewer than k nodes, it must remain in its original order.
• A single-node list should always be returned unchanged.

A naive implementation can easily lose references to parts of the list while reversing pointers, so careful pointer management is critical.

Approaches

Brute Force Approach

A straightforward solution is to extract nodes into an auxiliary data structure such as an array or stack. We could traverse the linked list group by group, collect k nodes, reverse their order inside the temporary structure, and reconnect them into the final list.

For example:

1. Traverse the list.
2. Store the next k nodes in an array.
3. Reverse the array.
4. Reconnect the reversed nodes.
5. Continue until the end of the list.

This approach works because arrays make reversal simple and direct. However, it uses additional memory proportional to the group size, and potentially proportional to the entire list depending on the implementation.

Although this is acceptable for the constraints, it does not satisfy the follow-up requirement of constant extra memory.

Optimal Approach

The key observation is that linked list reversal can already be done in-place using pointer manipulation. Instead of storing nodes externally, we can reverse each group directly inside the list.

The algorithm works by:

1. Finding whether a full group of k nodes exists.
2. Reversing those k nodes in-place.
3. Reconnecting the reversed group back into the list.
4. Repeating for the next group.

A dummy node is extremely useful because the head of the list itself may change after the first reversal.

This approach achieves:

• O(n) time complexity, because each node is visited a constant number of times
• O(1) extra space, because only pointer variables are used

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(k) or O(n)	Uses extra storage to reverse groups
Optimal	O(n)	O(1)	Reverses nodes in-place using pointer manipulation

Algorithm Walkthrough

Optimal In-Place Reversal Algorithm

1. Create a dummy node whose next points to the original head.

This simplifies edge cases where the first group reversal changes the head of the list. 2. Maintain a pointer called group_prev.

This pointer always represents the node immediately before the current group we want to reverse. 3. Find the kth node from group_prev.

Starting from group_prev, move forward k times. If we cannot reach the kth node, it means fewer than k nodes remain, so we stop processing. 4. Store the node after the kth node.

This node marks where the current group ends and where the next group begins. We call it group_next. 5. Reverse the current group.

Use the standard linked list reversal technique:

• Maintain prev and curr
• Reverse pointers one by one
• Stop once we reach group_next

During reversal:

• prev starts as group_next
• curr starts as the first node in the group

6. Reconnect the reversed group.

After reversal:

• The kth node becomes the new head of the group
• The original first node becomes the tail

Update:

• group_prev.next to point to the new group head
• Move group_prev to the tail of the reversed group

7. Repeat until no full group remains.

Why it works

The algorithm maintains the invariant that all nodes before group_prev are already correctly processed and connected. Each iteration reverses exactly one valid group of size k without disturbing the rest of the list. Because every reversal reconnects both the front and back boundaries correctly, the list always remains well-formed. When fewer than k nodes remain, the algorithm stops immediately, preserving the required order for leftover nodes.

Python Solution

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

from typing import Optional

class Solution:
    def reverseKGroup(
        self,
        head: Optional[ListNode],
        k: int
    ) -> Optional[ListNode]:

        dummy = ListNode(0)
        dummy.next = head

        group_prev = dummy

        while True:
            kth = group_prev

            # Find the kth node
            for _ in range(k):
                kth = kth.next
                if not kth:
                    return dummy.next

            group_next = kth.next

            # Reverse current group
            prev = group_next
            curr = group_prev.next

            while curr != group_next:
                temp = curr.next
                curr.next = prev
                prev = curr
                curr = temp

            # Reconnect reversed group
            temp = group_prev.next
            group_prev.next = kth
            group_prev = temp

The implementation begins by creating a dummy node. This avoids special handling when the first group reversal changes the head of the list.

The variable group_prev always points to the node before the current group. We repeatedly search for the kth node ahead of it. If the kth node does not exist, the remaining nodes are fewer than k, so the algorithm terminates.

Once a valid group is identified, the code performs an in-place reversal using the standard iterative reversal technique. The key trick is initializing prev to group_next, which automatically reconnects the reversed group to the remaining list during reversal.

After reversal completes:

• kth becomes the new head of the group
• The original group head becomes the tail

The final reconnect step updates the surrounding pointers and advances group_prev to prepare for the next iteration.

Go Solution

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseKGroup(head *ListNode, k int) *ListNode {
	dummy := &ListNode{Next: head}

	groupPrev := dummy

	for {
		kth := groupPrev

		// Find kth node
		for i := 0; i < k; i++ {
			kth = kth.Next
			if kth == nil {
				return dummy.Next
			}
		}

		groupNext := kth.Next

		// Reverse current group
		prev := groupNext
		curr := groupPrev.Next

		for curr != groupNext {
			temp := curr.Next
			curr.Next = prev
			prev = curr
			curr = temp
		}

		// Reconnect reversed group
		temp := groupPrev.Next
		groupPrev.Next = kth
		groupPrev = temp
	}
}

The Go implementation follows exactly the same logic as the Python solution. The primary differences are related to syntax and pointer handling.

Go uses explicit pointer types such as *ListNode, while Python references objects implicitly. In Go, nil checks are required instead of Python's None checks.

Because Go uses static typing, variable declarations are explicit and memory references are more visible. Otherwise, the overall algorithm and pointer manipulation strategy are identical.

Worked Examples

Example 1

Input:

head = [1,2,3,4,5]
k = 2

Initial list:

dummy -> 1 -> 2 -> 3 -> 4 -> 5

First Group

Group to reverse:

1 -> 2

Step	curr	prev	Result
Start	1	3	1 -> 3
Next	2	1	2 -> 1 -> 3

After reconnection:

dummy -> 2 -> 1 -> 3 -> 4 -> 5

Second Group

Group to reverse:

3 -> 4

Step	curr	prev	Result
Start	3	5	3 -> 5
Next	4	3	4 -> 3 -> 5

After reconnection:

dummy -> 2 -> 1 -> 4 -> 3 -> 5

Only one node remains, so processing stops.

Final output:

[2,1,4,3,5]

Example 2

Input:

head = [1,2,3,4,5]
k = 3

Initial group:

1 -> 2 -> 3

Reversal Process

Step	curr	prev	Result
Start	1	4	1 -> 4
Next	2	1	2 -> 1 -> 4
Next	3	2	3 -> 2 -> 1 -> 4

After reconnection:

dummy -> 3 -> 2 -> 1 -> 4 -> 5

The remaining nodes [4,5] contain fewer than 3 nodes, so they remain unchanged.

Final output:

[3,2,1,4,5]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each node is visited and reversed at most once
Space	O(1)	Only a constant number of pointer variables are used

The algorithm performs a constant amount of work per node. Although we repeatedly search for the kth node, every node participates in at most one reversal and one traversal step, so the total work remains linear.

No auxiliary arrays, stacks, or recursive calls are used, so the extra memory usage stays constant.

Test Cases

# Helper utilities for testing

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def build_list(values):
    dummy = ListNode()
    current = dummy

    for value in values:
        current.next = ListNode(value)
        current = current.next

    return dummy.next

def to_list(head):
    result = []

    while head:
        result.append(head.val)
        head = head.next

    return result

solution = Solution()

# Example 1
head = build_list([1, 2, 3, 4, 5])
assert to_list(solution.reverseKGroup(head, 2)) == [2, 1, 4, 3, 5]  # reverse in pairs

# Example 2
head = build_list([1, 2, 3, 4, 5])
assert to_list(solution.reverseKGroup(head, 3)) == [3, 2, 1, 4, 5]  # leftover nodes remain

# Single node
head = build_list([1])
assert to_list(solution.reverseKGroup(head, 1)) == [1]  # minimal input

# k equals list length
head = build_list([1, 2, 3, 4])
assert to_list(solution.reverseKGroup(head, 4)) == [4, 3, 2, 1]  # entire list reversed

# k greater than remaining nodes
head = build_list([1, 2, 3, 4, 5])
assert to_list(solution.reverseKGroup(head, 4)) == [4, 3, 2, 1, 5]  # last node untouched

# k = 1
head = build_list([1, 2, 3])
assert to_list(solution.reverseKGroup(head, 1)) == [1, 2, 3]  # no changes

# Even number of nodes
head = build_list([1, 2, 3, 4, 5, 6])
assert to_list(solution.reverseKGroup(head, 2)) == [2, 1, 4, 3, 6, 5]  # all groups reversed

# Odd number of nodes with incomplete tail
head = build_list([1, 2, 3, 4, 5, 6, 7])
assert to_list(solution.reverseKGroup(head, 3)) == [3, 2, 1, 6, 5, 4, 7]  # final node preserved

Test	Why
[1,2,3,4,5], k=2	Validates standard pair reversal
[1,2,3,4,5], k=3	Validates leftover nodes remain unchanged
[1], k=1	Tests smallest possible input
[1,2,3,4], k=4	Tests full-list reversal
[1,2,3,4,5], k=4	Tests incomplete final group
[1,2,3], k=1	Ensures no reversal occurs
[1,2,3,4,5,6], k=2	Tests multiple complete reversals
[1,2,3,4,5,6,7], k=3	Tests odd-length list with leftover tail

Edge Cases

Case 1: k = 1

When k equals 1, every group contains only one node. Reversing a single node does nothing, so the output should match the input exactly.

A careless implementation might still perform unnecessary pointer manipulation or accidentally break links. This implementation handles the case naturally because reversing a group of one node leaves the structure unchanged.

Case 2: Remaining Nodes Fewer Than k

Suppose the list is:

1 -> 2 -> 3 -> 4 -> 5

with k = 3.

After reversing the first three nodes, only two nodes remain. The problem explicitly states these leftover nodes must stay in their original order.

The algorithm safely handles this by searching for the kth node before attempting reversal. If fewer than k nodes remain, it immediately returns without modifying the remaining portion of the list.

Case 3: Entire List Length Equals k

If the list length is exactly equal to k, the whole list should be reversed once.

This is a common source of off-by-one pointer bugs because the reversed group becomes the entire output list. The dummy node prevents issues here because it provides a stable node before the head, allowing the algorithm to reconnect the reversed group correctly even when the head changes.