How to Reverse a Linked List in Groups of k Nodes: Recursive and Iterative Solutions

Question

Learn to reverse a linked list in groups of k nodes with recursive and iterative solutions. Master reversing segments and reconnecting them efficiently.

Accepted Answer

Reverse a linked list in groups of k nodes by traversing to locate each k-length segment, reversing the internal pointers of that segment, and reconnecting the reversed chunk back to the main list, leaving the final partial segment unchanged.

Reversing a singly linked list in fixed-size chunks is a fundamental algorithmic challenge that tests pointer manipulation and edge-case handling. The labuladong/fucking-algorithm repository provides a detailed implementation in 高频面试系列/k个一组反转链表.md, offering both recursive and iterative solutions with complete Java code.

Understanding the Problem Structure

The algorithm must process the linked list sequentially, identifying segments of exactly k nodes. For each complete segment:

Reverse the internal direction of the k nodes
Connect the reversed segment back to the previous part of the list
Proceed to the next segment

If the remaining nodes are fewer than k, they remain in original order. This requires careful tracking of segment boundaries to maintain list connectivity.

Recursive Approach

The recursive solution in 高频面试系列/k个一组反转链表.md follows a clean divide-and-conquer pattern. It treats each k-node block as a subproblem, reversing the current segment and delegating the remainder to the recursive call.

Locating the k-th Node

First, the algorithm verifies that a full segment exists by advancing a pointer k times from the current head. If the traversal reaches null before counting to k, the function returns the current head unchanged, preserving the partial tail.

Reversing the Segment

Once the k-th node is confirmed, the algorithm isolates the segment and reverses it using the standard three-pointer technique (prev, curr, next). This flips the next pointers of all nodes within the [head, k-th node] range.

Stitching Segments Together

After reversal, the original head (now the tail of the reversed segment) must connect to the result of recursively processing the remainder of the list. The function returns the new head of the reversed segment (previously the k-th node), which becomes the entry point for the previous recursive level.

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public ListNode reverseKGroup(ListNode head, int k) {
    if (head == null || k <= 1) return head;
    
    // Check if we have k nodes remaining
    ListNode kth = head;
    for (int i = 1; i < k && kth != null; i++) {
        kth = kth.next;
    }
    if (kth == null) return head; // Less than k nodes left
    
    // Reverse current segment
    ListNode nextGroup = kth.next;
    ListNode prev = null;
    ListNode curr = head;
    while (curr != nextGroup) {
        ListNode nxt = curr.next;
        curr.next = prev;
        prev = curr;
        curr = nxt;
    }
    
    // head is now tail, connect to next group
    head.next = reverseKGroup(nextGroup, k);
    return kth; // kth is new head of this segment
}

Iterative Approach

For production environments where recursion depth might cause stack overflow on extremely long lists, the repository provides an iterative implementation using a dummy node pattern. This approach processes segments in a loop without consuming call stack space.

The algorithm maintains a groupPrev pointer that marks the node immediately preceding the current segment. For each iteration:

Locate the k-th node from groupPrev using the getKthNode helper
If fewer than k nodes remain, terminate the loop
Reverse the segment between groupPrev.next and the k-th node
Advance groupPrev to the tail of the just-reversed segment (which was the original head)

public ListNode reverseKGroupIterative(ListNode head, int k) {
    if (head == null || k <= 1) return head;
    
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode groupPrev = dummy;
    
    while (true) {
        // Check if we have k nodes left
        ListNode kth = getKthNode(groupPrev, k);
        if (kth == null) break;
        
        ListNode groupNext = kth.next;
        
        // Reverse the nodes in [groupPrev.next, kth]
        ListNode prev = groupPrev.next;
        ListNode curr = prev.next;
        while (curr != groupNext) {
            ListNode nxt = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nxt;
        }
        
        // Move groupPrev to the tail of reversed segment (original head)
        ListNode first = groupPrev.next;
        groupPrev.next = kth;
        first.next = groupNext;
        groupPrev = first;
    }
    
    return dummy.next;
}

private ListNode getKthNode(ListNode start, int k) {
    ListNode cur = start;
    for (int i = 0; i < k; i++) {
        if (cur.next == null) return null;
        cur = cur.next;
    }
    return cur;
}

Complexity Analysis

Both implementations from 高频面试系列/k个一组反转链表.md achieve optimal efficiency:

Time Complexity: O(N) where N is the total number of nodes. Each node is visited a constant number of times (once during location, once during reversal).
Space Complexity:
- Recursive version: O(N/k) due to the call stack depth (one frame per k-node segment).
- Iterative version: O(1) extra space (excluding the dummy node), making it preferable for very long lists.

Summary

Reverse a linked list in groups of k by processing the list in k-node segments, reversing each complete segment while leaving partial tails unchanged.
The recursive solution in labuladong/fucking-algorithm provides elegant divide-and-conquer logic but consumes O(N/k) stack space.
The iterative solution uses a dummy node and runs in O(1) extra space, making it the preferred choice for production environments with strict memory constraints.
Always verify segment length before reversal to handle edge cases where the list length is not divisible by k.

Frequently Asked Questions

What happens if the linked list length is not divisible by k?

If the final segment contains fewer than k nodes, it remains in its original order. The algorithm checks for the k-th node before reversing any segment; if the traversal reaches null before counting to k, it returns the current head unchanged, preserving the partial tail as specified in the problem requirements.

Is the recursive or iterative solution better for production code?

The iterative solution is generally preferred for production environments because it uses O(1) extra space versus the recursive version's O(N/k) call stack depth. For extremely long lists (millions of nodes), deep recursion risks stack overflow errors, whereas the iterative dummy-node approach processes the list in a single loop without consuming stack frames.

How does the dummy node simplify edge case handling?

The dummy node acts as a placeholder preceding the actual head of the list, eliminating special-case logic for the first segment. Without a dummy node, reversing the initial k nodes requires separate handling to update the list's head pointer. The dummy ensures groupPrev always has a valid node to link from, unifying the logic for the first, middle, and last segments.

Can this algorithm be modified to reverse every other k nodes?

Yes, the algorithm can be adapted by adding a toggle flag or counter that alternates between reversing and skipping segments. After reversing one k-node group, you would advance the pointer by k nodes without reversing the next group, then continue alternating. This modification maintains the same O(N) time complexity while achieving the "reverse every other k" pattern.