NUHMAN.com

Introduction

LeetCode 25: Reverse Nodes in k-Group is a challenging linked list problem that requires reversing nodes in groups of k. Unlike simple list reversal, it adds a constraint that only full groups of k should be reversed—leaving remaining nodes as-is.

This problem strengthens your understanding of linked list manipulation, pointer juggling, and recursive/iterative segment processing.

Problem Statement

Given the head of a linked list, reverse the nodes of the list k at a time, and return the modified list. If the number of nodes is not a multiple of k, leave the remaining nodes as-is.

You may not alter the values in the nodes, only nodes themselves may be changed.

Examples

go

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

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

Approach: Segment-Wise Reversal with Recursion

1. Count k nodes from the current head. If fewer than k, return head as-is.
2. Reverse those k nodes.
3. Recursively call the function on the next segment.
4. Connect the reversed portion to the result of the recursion.

Go Implementation

go

package main

import (
    "fmt"
)

// Definition for singly-linked list.
type ListNode struct {
    Val  int
    Next *ListNode
}

func reverseKGroup(head *ListNode, k int) *ListNode {
    count := 0
    current := head

    // First, check if there are at least k nodes
    for current != nil && count < k {
        current = current.Next
        count++
    }

    if count < k {
        return head
    }

    // Reverse k nodes
    var prev *ListNode
    current = head
    for i := 0; i < k; i++ {
        next := current.Next
        current.Next = prev
        prev = current
        current = next
    }

    // Recursively reverse the rest and connect
    head.Next = reverseKGroup(current, k)
    return prev
}

Helper Functions for Testing

go

func createList(nums []int) *ListNode {
    dummy := &ListNode{}
    curr := dummy
    for _, val := range nums {
        curr.Next = &ListNode{Val: val}
        curr = curr.Next
    }
    return dummy.Next
}

func printList(head *ListNode) {
    for head != nil {
        fmt.Print(head.Val)
        if head.Next != nil {
            fmt.Print(" -> ")
        }
        head = head.Next
    }
    fmt.Println()
}

func main() {
    head := createList([]int{1, 2, 3, 4, 5})
    k := 3
    fmt.Print("Original List: ")
    printList(head)

    result := reverseKGroup(head, k)
    fmt.Printf("Reversed in groups of %d: ", k)
    printList(result)
}

Step-by-Step (Example: k = 2)

Original:

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

Step 1: Reverse first two:

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

Step 2: Reverse next two:

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

Final Result:

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

Time and Space Complexity

• Time Complexity: O(n), where n is the total number of nodes.
• Space Complexity: O(n/k) due to recursion depth (can be optimized with iteration).

Key Takeaways

• You must check for k-sized groups before attempting to reverse.
• Use classic in-place reversal with three pointers.
• A recursive or iterative approach works—recursive is elegant, iterative is more stack-safe.