Reverse Nodes in k-Group (LeetCode 25)

The problem

You get the head of a linked list and a positive integer k. Reverse the nodes in each consecutive block of k, and return the new head. If the number of nodes left at the end is less than k, leave those nodes in their original order. Only change links, not values.

Input:  1 -> 2 -> 3 -> 4 -> 5,  k = 2
Output: 2 -> 1 -> 4 -> 3 -> 5

Blocks (1, 2) and (3, 4) are reversed; 5 is a partial block, so it stays.

How to think about it

Start with brute force. Copy the values into an array, reverse each full chunk of k, and write them back. O(n) time but O(n) space, and it changes values, which is not allowed.

The key insight: this is the basic reversal, run once per block, plus careful stitching. For each block you need to know four things: groupPrev (the node just before the block), the block’s first node, kth (its last node), and groupNext (the node after it). Reverse the block in place, then fix the two boundaries: groupPrev should now point at kth (the new front), and the old first node, now at the back, should point at groupNext.

Look ahead before you reverse. Walk k steps from groupPrev to find kth. If you fall off the end first, there aren’t k nodes left, so stop and return. This is what keeps the short tail untouched.

A neat trick for the back boundary: start the reversal with prev = groupNext instead of None. Then the first node of the block, once flipped, points straight at groupNext, and you don’t have to set it separately.

Which pattern is this? Linked-list in-place reversal. The tell is “reverse in groups of k”. A dummy head handles the fact that the first block changes the head.

Approach

1. Create d = ListNode(0, head); set groupPrev = d.
2. Loop:
   • walk k steps from groupPrev to find kth; if you hit None, return d.next,
   • set groupNext = kth.next,
   • reverse the block with prev = groupNext, cur = groupPrev.next, flipping until cur reaches groupNext,
   • save tmp = groupPrev.next (the old first node, now last), set groupPrev.next = kth, and move groupPrev = tmp.

Solution

class ListNode:                                   # LeetCode's node type
    def __init__(self, val=0, next=None):
        self.val = val; self.next = next

def reverse_k_group(head, k):
    d = ListNode(0, head); groupPrev = d
    while True:
        kth = groupPrev
        for _ in range(k):                        # is there a full group of k?
            kth = kth.next
            if not kth: return d.next             # no: leave the remainder alone
        groupNext = kth.next; prev, cur = groupNext, groupPrev.next   # prev starts at groupNext
        while cur is not groupNext:               # standard reversal inside the block
            cur.next, prev, cur = prev, cur, cur.next
        tmp = groupPrev.next; groupPrev.next = kth; groupPrev = tmp   # reconnect front, advance
# reverse_k_group([1,2,3,4,5], 2) -> [2,1,4,3,5]

Dry run

On 1 -> 2 -> 3 -> 4 -> 5, k = 2:

In round 3 the look-ahead runs off the end after one step, so 5 is left alone.

Complexity

• Time: O(n). Each node is visited twice: once by the look-ahead and once by the reversal.
• Space: O(1). A fixed set of pointers. A recursive solution would use O(n/k) stack.

Edge cases and pitfalls

• k = 1: each block is one node; reversing it changes nothing, and the list comes back unchanged.
• Length a multiple of k: every block is reversed, then the next look-ahead hits None and returns.
• Partial last block: must stay in original order. Reversing it is the most common bug.
• Starting the reversal with prev = None. Then the block’s last node points to None and the rest of the list is cut off, unless you reconnect it separately.
• Advancing groupPrev to kth. After reversal, kth is at the front; the node before the next block is the old first node, tmp.

Related problems

• Swap Nodes in Pairs (LeetCode 24): this problem with k = 2.
• Reverse Linked List II (LeetCode 92): reverse a single block given by positions.
• Reverse Linked List (LeetCode 206): the flip used inside each block.