Reverse a Linked List in K-Node Groups – Go Solution for Interviews

Problem Overview

The task is to reverse a singly‑linked list in groups of k nodes. The author likens the process to cutting slices from a cake: each bite (segment) is taken, reversed, and the remaining cake stays unchanged until the next bite.

Solution Idea

Identify the head and tail of each k -node segment.

Reverse that segment in place.

Connect the reversed segment to the result of recursively processing the next segment.

When every segment has been processed, the entire list is reversed in k -node groups.

Algorithm Details

The main function reverseKGroup receives the list head and the integer k. Two pointers, a and b, start at the head. A loop advances

b

k

steps; if b becomes nil before completing the steps, the remaining nodes are left unchanged and the original head is returned.

Once a full segment is located, the helper reverse is called to reverse nodes from a up to (but not including) b. The returned node last becomes the new head of this segment. The original start node a now points to the result of reverseKGroup(b, k), linking the reversed segment with the rest of the list. Finally, last is returned as the head of the processed list.

Helper Function

reverse

reverses a sub‑list defined by the exclusive range [a, b). It iteratively moves each node to the front of a new list using a temporary pointer, updating pre until a == b, then returns pre as the new head of the reversed segment.

Complete Go Implementation

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseKGroup(head *ListNode, k int) *ListNode {
    a, b := head, head
    // locate a segment of length k
    for i := 0; i < k; i++ {
        if b == nil {
            return head
        }
        b = b.Next
    }
    // reverse the segment [a, b)
    last := reverse(a, b)
    // connect the tail of the reversed segment to the next processed part
    a.Next = reverseKGroup(b, k)
    return last
}

// reverse sub‑list [a, b) and return new head
func reverse(a, b *ListNode) *ListNode {
    var pre *ListNode = nil
    for a != b {
        temp := a
        a = a.Next
        temp.Next = pre
        pre = temp
    }
    return pre
}

Explanation of the Process

The algorithm works recursively: each call processes the first k nodes, reverses them, and attaches the result of the next recursive call. The base case occurs when fewer than k nodes remain, in which case the original order is preserved.

This approach runs in O(n) time, where n is the number of nodes, and uses O(1) extra space aside from the recursion stack.