LeetCode 25: Reverse Nodes in k-Group Solution in Python Explained

Problem Statement

LeetCode 25, Reverse Nodes in k-Group, is a hard-level challenge where you’re given the head of a linked list and an integer k. Your task is to reverse every group of k nodes in the list and return the head of the modified list. If the remaining nodes are fewer than k, leave them as-is. You must reverse the nodes themselves, not just their values.

Constraints

Number of nodes in the list is between 1 and 5000.
0 <= Node.val <= 1000: Node values range from 0 to 1000.
1 <= k <= list length: k is positive and within list bounds.

Example

Input: head = [1,2,3,4,5], k = 2
Output: [2,1,4,3,5]
Explanation: Reverse groups of 2: [1,2] → [2,1], [3,4] → [4,3], [5] stays.

Input: head = [1,2,3,4,5], k = 3
Output: [3,2,1,4,5]
Explanation: Reverse [1,2,3] → [3,2,1], [4,5] stays.

Input: head = [1], k = 1
Output: [1]
Explanation: Group of 1 stays as-is.

Understanding the Problem

How do you solve LeetCode 25: Reverse Nodes in k-Group in Python? Imagine a linked list like [1,2,3,4,5] with k = 2. You need to reverse each group of 2 nodes—[1,2] becomes [2,1], [3,4] becomes [4,3], and [5] stays—resulting in [2,1,4,3,5]. For k = 3, reverse [1,2,3] to [3,2,1], leaving [4,5], yielding [3,2,1,4,5]. Since it’s a linked list, we manipulate pointers to reverse groups, and we’ll explore two methods: an Iterative Approach (using pointers) and a Recursive Approach (using function calls).

Solution 1: Iterative Approach (Primary)

Explanation

Use pointers to reverse each k-group iteratively, tracking group boundaries and linking them correctly. Check group length before reversing, leaving short groups unchanged.

Here’s a visual for [1,2,3,4], k = 2:

Before: dummy -> 1 -> 2 -> 3 -> 4
Reverse 1-2: dummy -> 2 -> 1 -> 3 -> 4
Reverse 3-4: dummy -> 2 -> 1 -> 4 -> 3

Handle Edge Case.

If list is empty or k = 1, return head.

Create Dummy Node.

Use a dummy to simplify linking.

Count Group Length.

Check if k nodes exist before reversing.

Reverse k Nodes.

Use pointers to reverse group, link to previous group.

Move to Next Group.

Update pointers, repeat until list ends.

Return Head.

Return dummy.next.

Step-by-Step Example

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

We have [1,2,3,4,5] and want [2,1,4,3,5].

Goal: Reverse groups of 2.
Result for Reference: [2,1,4,3,5].
Start: Dummy -> 1 -> 2 -> 3 -> 4 -> 5, prev = dummy.
Step 1: Check edge case.

List not empty, k > 1, proceed.

Step 2: Count first k = 2 nodes.

Start at 1, count 2 nodes (1,2), enough, proceed.

Step 3: Reverse [1,2].

curr = 1, next_node = 2, next_next = 3.
Reverse: 2.next = 1, 1.next = 3.
Link prev (dummy) to 2.
List: dummy -> 2 -> 1 -> 3 -> 4 -> 5.
Move prev to 1, curr to 3.

Step 4: Count next k = 2 nodes.

From 3, count 2 (3,4), proceed.

Step 5: Reverse [3,4].

curr = 3, next_node = 4, next_next = 5.
Reverse: 4.next = 3, 3.next = 5.
Link prev (1) to 4.
List: dummy -> 2 -> 1 -> 4 -> 3 -> 5.
Move prev to 3, curr to 5.

Step 6: Count next k = 2.

Only 5 left, less than 2, stop.

Finish: Return dummy.next: [2,1,4,3,5].

How the Code Works (Iterative)

Here’s the Python code with line-by-line explanation:

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

def reverseKGroup(head: ListNode, k: int) -> ListNode:
    # Line 1: Check if list empty or k=1
    if not head or k == 1:
        # Line 2: Return head as-is
        return head

    # Line 3: Create dummy node
    dummy = ListNode(0)
    # Line 4: Link dummy to head
    dummy.next = head
    # Line 5: Prev pointer starts at dummy
    prev = dummy

    # Line 6: Loop through list
    while prev.next:
        # Line 7: Current starts at next node
        curr = prev.next
        # Line 8: Count k nodes
        count = 0
        temp = curr
        # Line 9: Count nodes until k or end
        while temp and count < k:
            count += 1
            temp = temp.next
        # Line 10: If fewer than k, stop
        if count < k:
            break

        # Line 11: Next group start
        next_group = temp
        # Line 12: Reverse k nodes
        prev_node = next_group
        for _ in range(k):
            # Line 13: Save next node
            next_node = curr.next
            # Line 14: Reverse link
            curr.next = prev_node
            # Line 15: Update prev_node
            prev_node = curr
            # Line 16: Move curr forward
            curr = next_node
        # Line 17: Save start of current group
        temp = prev.next
        # Line 18: Link prev to reversed group
        prev.next = prev_node
        # Line 19: Move prev to end of reversed group
        prev = temp

    # Line 20: Return modified list head
    return dummy.next

Alternative: Recursive Approach

Explanation

Recursively reverse the first k nodes, then link to the result of reversing the next k-group. Use a helper to count nodes and reverse k at a time.

Base Case.

If fewer than k nodes, return as-is.

Reverse k Nodes.

Reverse first k nodes manually.

Recurse.

Link kth node to result of reversing rest.

Return New Head.

Return head of reversed group.

Step-by-Step Example (Recursive)

For head = [1,2,3,4], k = 2:

Goal: Reverse to [2,1,4,3].
Result for Reference: [2,1,4,3].
Step 1: reverseKGroup(1->2->3->4, 2).

Count 2 nodes (1,2), enough.
Reverse: 2 -> 1, 1.next = reverseKGroup(3->4, 2).

Step 2: reverseKGroup(3->4, 2).

Count 2 nodes, reverse: 4 -> 3.
3.next = reverseKGroup(null, 2) = null.
Return 4->3.

Step 3: Back to step 1.

1.next = 4->3.
Return 2->1->4->3.

Finish: [2,1,4,3].

How the Code Works (Recursive)

Here’s the recursive Python code with explanations:

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

def reverseKGroupRecursive(head: ListNode, k: int) -> ListNode:
    # Line 1: Count k nodes
    count = 0
    curr = head
    # Line 2: Loop to count k or end
    while curr and count < k:
        count += 1
        curr = curr.next
    # Line 3: If fewer than k, return head
    if count < k:
        return head

    # Line 4: Reverse k nodes
    prev = None
    curr = head
    # Line 5: Reverse k nodes in loop
    for _ in range(k):
        # Line 6: Save next node
        next_node = curr.next
        # Line 7: Reverse link
        curr.next = prev
        # Line 8: Move prev and curr
        prev = curr
        curr = next_node

    # Line 9: Save new head (prev)
    new_head = prev
    # Line 10: Recursively reverse next k-group
    head.next = reverseKGroupRecursive(curr, k)
    # Line 11: Return new head of this group
    return new_head

Complexity

Iterative:

Time: O(n) – Single pass, n is list length.
Space: O(1) – Only pointers.

Recursive:

Time: O(n) – O(n/k) recursive calls, O(k) per call.
Space: O(n/k) – Recursion stack depth.

Efficiency Notes

Both solutions run in O(n) time, but iterative uses O(1) space, making it more memory-efficient. Recursive is elegant but uses stack space, less optimal for very long lists.

Key Insights

Tips to master LeetCode 25:

Count Before Reverse: Always check k nodes exist—don’t assume!
Pointers are Crucial: Both methods rely on precise link adjustments.
Group by Group: Focus on k at a time—break it down!

Additional Example

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

Goal: Reverse to [3,2,1,4,5].
Iterative: Dummy -> 3 -> 2 -> 1 -> 4 -> 5.
Recursive: 3 -> 2 -> 1 -> swap(4->5) -> 4 -> 5.
Result: [3,2,1,4,5].

Edge Cases

Single Node: [1], k = 1 – Returns [1].
Exact k: [1,2], k = 2 – Returns [2,1].
Short End: [1,2,3], k = 2 – Returns [2,1,3].

Final Thoughts

The iterative approach is efficient and practical for LeetCode 25 in Python, while recursive offers a clean alternative. Check LeetCode 24: Swap Nodes in Pairs for simpler swapping!