LeetCode 25: Reverse Nodes in k-Group

Problem Restatement

We are given the head of a linked list and an integer k.

We need to reverse the nodes of the list k at a time and return the modified list.

If the number of remaining nodes at the end is fewer than k, those nodes must stay in the same order.

We may not change node values. We may only change node links.

For example:

1 -> 2 -> 3 -> 4 -> 5
k = 2

becomes:

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

The constraints say 1 <= k <= n <= 5000, and node values are between 0 and 1000. The follow-up asks for O(1) extra memory.

Input and Output

Example function shape:

def reverseKGroup(head: ListNode, k: int) -> ListNode:
    ...

Examples

Example 1:

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

Reverse each complete group of two:

[1,2] -> [2,1]
[3,4] -> [4,3]
[5]   -> unchanged

Output:

[2,1,4,3,5]

Example 2:

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

Reverse the first three nodes:

[1,2,3] -> [3,2,1]

Only two nodes remain, so they stay unchanged:

[4,5]

Output:

[3,2,1,4,5]

First Thought: Copy Values Into an Array

One easy idea is:

1. Copy all node values into an array.
2. Reverse every group of k values.
3. Write the values back into the linked list.

This is simpler than pointer manipulation.

But the problem forbids changing values only. We must change the nodes themselves.

So this approach does not satisfy the requirement.

Key Insight

We can process one group at a time.

For each group:

1. Check whether there are at least k nodes.
2. Reverse exactly those k nodes.
3. Connect the reversed group back to the previous part and the next part.
4. Move to the next group.

A dummy node helps with the first group because the head changes after reversal.

Before reversing one group:

group_prev -> 1 -> 2 -> 3 -> next_group

For k = 3, after reversing:

group_prev -> 3 -> 2 -> 1 -> next_group

The node 1, which was the old group head, becomes the tail of the reversed group.

Visual Walkthrough

Use:

head = 1 -> 2 -> 3 -> 4 -> 5
k = 2

Create:

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

First group:

1 -> 2

Reverse it:

2 -> 1

Reconnect:

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

Now group_prev becomes 1.

Second group:

3 -> 4

Reverse it:

4 -> 3

Reconnect:

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

Only one node remains:

5

Since fewer than k nodes remain, leave it unchanged.

Final result:

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

Algorithm

1. Create a dummy node pointing to head.
2. Let group_prev = dummy.
3. Repeatedly find the kth node after group_prev.
4. If no kth node exists, stop.
5. Let group_next = kth.next.
6. Reverse nodes from group_prev.next up to before group_next.
7. Reconnect the reversed group:
   • old group head becomes group tail
   • group_prev.next becomes the new group head
8. Move group_prev to the tail of the reversed group.
9. Return dummy.next.

Correctness

At the start of each iteration, all nodes before group_prev have already been processed correctly.

The algorithm first checks whether a complete group of k nodes exists. If fewer than k nodes remain, it stops and leaves them unchanged, as required.

For a complete group, the algorithm reverses exactly the nodes from group_prev.next through the kth node. It uses group_next as the boundary, so nodes after the group are not changed.

After reversal, the old group head becomes the group tail, and the old kth node becomes the group head. The algorithm reconnects the previous processed part to the new group head and reconnects the new group tail to the next unprocessed part.

Then group_prev moves to the tail of the reversed group, so the invariant holds for the next group.

Therefore every complete group of k nodes is reversed exactly once, and the final incomplete group remains unchanged.

Complexity

Implementation

from typing import Optional

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

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

        while True:
            kth = self.get_kth(group_prev, k)

            if not kth:
                break

            group_next = kth.next

            prev = group_next
            current = group_prev.next

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

            old_group_head = group_prev.next
            group_prev.next = kth
            group_prev = old_group_head

        return dummy.next

    def get_kth(
        self,
        current: Optional[ListNode],
        k: int
    ) -> Optional[ListNode]:
        while current and k > 0:
            current = current.next
            k -= 1

        return current

Code Explanation

Create a dummy node:

dummy = ListNode(0, head)

This handles reversal of the first group.

group_prev points to the node before the group we want to reverse:

group_prev = dummy

Find the kth node after group_prev:

kth = self.get_kth(group_prev, k)

If there are fewer than k nodes left:

if not kth:
    break

Save the node after the group:

group_next = kth.next

Reverse the group using standard linked-list reversal:

prev = group_next
current = group_prev.next

The boundary is group_next, so the loop reverses only the current group:

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

After reversal, kth is the new head of the group.

The old group head becomes the tail:

old_group_head = group_prev.next

Reconnect the previous part:

group_prev.next = kth

Move to the next group:

group_prev = old_group_head

Finally:

return dummy.next

Testing

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

def run_tests():
    s = Solution()

    head = build_list([1, 2, 3, 4, 5])
    assert to_list(s.reverseKGroup(head, 2)) == [2, 1, 4, 3, 5]

    head = build_list([1, 2, 3, 4, 5])
    assert to_list(s.reverseKGroup(head, 3)) == [3, 2, 1, 4, 5]

    head = build_list([1, 2, 3, 4])
    assert to_list(s.reverseKGroup(head, 4)) == [4, 3, 2, 1]

    head = build_list([1, 2, 3])
    assert to_list(s.reverseKGroup(head, 1)) == [1, 2, 3]

    head = build_list([1])
    assert to_list(s.reverseKGroup(head, 1)) == [1]

    print("all tests passed")

run_tests()