Reverse Nodes in k-Group

Problem

Given the head of a singly-linked list and an integer k, reverse the nodes in blocks of exactly k: reverse the first k nodes among themselves, then the next k, and so on. If fewer than k nodes remain at the end, that tail block keeps its original order.

Two constraints make this hard. You must relink the actual nodes (swapping the values inside nodes is not allowed), and the follow-up asks for O(1) extra memory: no arrays, no recursion stack.

Examples

• Input: head = [1, 2, 3, 4, 5], k = 2 → Output: [2, 1, 4, 3, 5] Blocks (1,2) and (3,4) are each reversed; the leftover 5 is a partial block and stays put.
• Input: head = [1, 2, 3, 4, 5], k = 3 → Output: [3, 2, 1, 4, 5] Only (1,2,3) forms a full block; (4,5) has fewer than 3 nodes and is untouched.
• Input: head = [1, 2, 3, 4, 5, 6], k = 1 → Output: [1, 2, 3, 4, 5, 6] Reversing blocks of one changes nothing.

Constraints

• Number of nodes n is in [1, 5000], and 1 <= k <= n.
• 0 <= Node.val <= 1000.
• Follow-up target for the expected answer: O(n) time, O(1) extra space, with the nodes themselves rewired.

Think about it first

TL;DR

Iterative block-by-block pointer reversal behind a dummy node — O(n) time, O(1) space (recursive version: O(n) time, O(n/k) stack).

Approach 1 — Brute force: array of nodes

Load every node into a Python list, reverse each complete k-slice of the array, then rewire all next pointers to follow the array order. This relinks real nodes (no value swapping) but uses O(n) extra memory.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
from typing import Optional

def reverseKGroup(head: Optional[ListNode], k: int) -> Optional[ListNode]:
    nodes = []
    node = head
    while node:
        nodes.append(node)
        node = node.next
    n = len(nodes)
    for start in range(0, n - n % k, k):
        chunk = nodes[start:start + k]
        chunk.reverse()
        nodes[start:start + k] = chunk
    for i in range(n - 1):
        nodes[i].next = nodes[i + 1]
    nodes[n - 1].next = None
    return nodes[0]

Time O(n), space O(n). The constraints (n ≤ 5000) allow it, but it fails the follow-up: it uses linear extra memory where the problem asks for O(1), and it sidesteps the pointer manipulation being tested.

Approach 2 — Recursion, one block per call

The insight: the problem is self-similar. Reverse the first k nodes, then attach the processed remainder to them. If the recursive call returns the already-processed remainder, the current block’s reversal can seed prev with that result, and the links across the block boundary come out correct. The reversal itself is the standard three-pointer prev/curr/next walk that reverses a whole list.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
from typing import Optional

def reverseKGroup(head: Optional[ListNode], k: int) -> Optional[ListNode]:
    # Check there are k nodes; if not, leave this tail as is.
    node = head
    for _ in range(k):
        if not node:
            return head
        node = node.next
    # node is now the (k+1)-th node: the next block's head.
    prev = reverseKGroup(node, k)
    curr = head
    for _ in range(k):
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    return prev

Walkthrough on [1, 2, 3, 4, 5], k = 2: the first call verifies nodes 1–2 exist and recurses from node 3. That call recurses from node 5; the deepest call sees only one node — fewer than k — and returns 5 untouched. Unwinding: the (3,4) call reverses with prev = 5, producing 4 → 3 → 5, and returns 4. The (1,2) call reverses with prev = 4, producing 2 → 1 → 4, and returns 2. Final list: [2, 1, 4, 3, 5].

Time O(n) — each node is visited by one length check and one reversal. Space O(n/k) for the recursion stack (one frame per block), which fails the strict O(1) follow-up.

Approach 3 — Iterative with a dummy node, O(1) space

The insight: a block needs two anchors: group_prev, the node just before it, and group_next, the node just after its k-th node. Seed the three-pointer reversal with prev = group_next so the reversed block’s tail points at the rest of the list, then splice with group_prev.next = kth to attach it in front. The block’s old head becomes the new group_prev. A dummy node in front of the head keeps the first block from being a special case.

The anchors for the first block of [1, 2, 3, 4, 5] with k = 2:

flowchart LR
    dummy["dummy<br/>(group_prev)"] --> n1["1"]
    n1 --> n2["2<br/>(kth)"]
    n2 --> n3["3<br/>(group_next)"]
    n3 --> n4["4"]
    n4 --> n5["5"]

Reverse nodes 1 and 2 with prev seeded to node 3, then set group_prev.next = kth so dummy points at node 2. Node 1 becomes the new group_prev for the next block.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
from typing import Optional

def reverseKGroup(head: Optional[ListNode], k: int) -> Optional[ListNode]:
    dummy = ListNode(0, head)
    group_prev = dummy
    while True:
        # Find the k-th node of the current block.
        kth = group_prev
        for _ in range(k):
            kth = kth.next
            if not kth:
                return dummy.next  # partial block: leave it, done
        group_next = kth.next
        # Reverse the block, seeded so its tail ends at group_next.
        prev, curr = group_next, group_prev.next
        while curr is not group_next:
            nxt = curr.next
            curr.next = prev
            prev = curr
            curr = nxt
        # Splice the reversed block in; old head is the new tail.
        old_head = group_prev.next
        group_prev.next = kth
        group_prev = old_head

Walkthrough on [1, 2, 3, 4, 5], k = 2: group_prev = dummy. Block 1: kth = 2, group_next = 3; reversing 1, 2 with seed 3 yields 2 → 1 → 3; splice dummy.next = 2, group_prev = 1. List: 2, 1, 3, 4, 5. Block 2: from node 1, kth = 4, group_next = 5; reversing 3, 4 with seed 5 yields 4 → 3 → 5; splice 1.next = 4, group_prev = 3. List: 2, 1, 4, 3, 5. Block 3: the walk from node 3 hits None after one step — fewer than k nodes — so return dummy.next, i.e. [2, 1, 4, 3, 5].

Time O(n): each node is touched once by a k-th-node scan and once by a reversal. Space O(1): five pointers and a dummy node.

Common pitfalls

• Reversing the final partial block. Every approach must count k nodes before reversing; the leftover n mod k nodes keep their order. Tests always include one.
• Losing the cross-block link. After reversal the block’s old head is its new tail and must point at the next block’s (eventually reversed) head. Seeding the reversal with group_next (or the recursive result) handles this directly; reversing into None and patching afterward is a common source of bugs.
• Forgetting the dummy node. The list’s head changes (it becomes the first block’s k-th node); without a dummy, returning the new head and splicing the first block become special cases.
• Swapping values instead of nodes. It passes the visible tests and is explicitly banned by the problem — interviewers check for it.

Pattern takeaway

Segment-wise linked-list rewiring reduces to the same components: a dummy node so the head is not a special case, an anchor pointer just before the segment, a look-ahead scan to validate the segment length, and the three-pointer reversal seeded with whatever should follow the segment. Once the seeded reversal is clear (reverse into the successor rather than into None), multi-block problems become a loop of identical splices.