Linked List Group Reversal

Description

Group reversal reverses a linked list in pieces: k nodes at a time (Reverse Nodes in k-Group), or only the nodes between two positions (Reverse Linked List II). Both reuse the plain reversal loop. The new work is bookkeeping at the edges of each piece. You check that a group is complete before touching it, and you stitch each reversed piece back to the nodes before and after it.

We'll go from simple to more technical:

1. The pattern: reverse k at a time, only when k nodes remain.
2. A second flavor: reverse one subrange by repeatedly moving nodes to its front.
3. Where batch-at-a-time and edit-in-place processing show up.
4. The stitching bugs, and recursion depth on long lists.

The approach

Reversing a whole list is one loop. In groups of k, a short last group is usually left as it is. So first count ahead: are there k nodes? If not, return the rest unchanged. If so, reverse exactly those k nodes and connect the group's new tail to the rest of the list, which the recursion has already handled.

Reversing 4 -> 9 -> 2 -> 7 -> 5 -> 1 -> 8 in groups of 3:

The result is 2 -> 9 -> 4 -> 1 -> 5 -> 7 -> 8. Note the stitch: 4, which was the first group's head, is now its tail and must point to 1, the second group's new head.

ListNode reverseKGroup(ListNode head, int k) {
    ListNode node = head;
    int count = 0;
    while (node != null && count < k) { node = node.next; count++; }
    if (count < k) return head;              // fewer than k nodes left - leave unchanged

    ListNode newHead = reverseKGroup(node, k); // recursively handle everything after this group first
    ListNode curr = head;
    ListNode prev = newHead;
    for (int i = 0; i < k; i++) {              // reverse exactly this group of k nodes
        ListNode next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    return prev;   // the new head of this (now-reversed) group
}

def reverse_k_group(head: ListNode | None, k: int) -> ListNode | None:
    node = head
    count = 0
    while node is not None and count < k:
        node = node.next
        count += 1
    if count < k:
        return head                          # fewer than k nodes left - leave unchanged

    new_head = reverse_k_group(node, k)      # recursively handle everything after this group first
    curr = head
    prev = new_head
    for _ in range(k):                       # reverse exactly this group of k nodes
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    return prev   # the new head of this (now-reversed) group

Counting first is what keeps the short last group simple: it's an early return, not an undo. The recursion handles the rest of the list before this group is reversed. So prev starts out pointing at the already-finished remainder, and the reversal links the group straight into it.

A second flavor: reversing one subrange

Reversing only positions left to right needs a different move. Keep an anchor, prev, on the node just before the range. Keep curr on the range's first node; it will end up as the range's tail, so it never moves. Then, again and again, take the node right after curr and move it to the front of the range, right after the anchor.

Reversing positions 2 to 4 of 4 -> 9 -> 2 -> 7 -> 5 (the anchor is 4, curr is 9):

ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode prev = dummy;
for (int i = 0; i < left - 1; i++) prev = prev.next;   // prev: the anchor, fixed just before the range

ListNode curr = prev.next;   // curr: fixed at the range's ORIGINAL start - it becomes the range's tail
for (int i = 0; i < right - left; i++) {
    ListNode moved = curr.next;      // pull the node right after curr...
    curr.next = moved.next;
    moved.next = prev.next;          // ...and insert it right after the anchor
    prev.next = moved;
}
return dummy.next;

def reverse_between(head: ListNode | None, left: int, right: int) -> ListNode | None:
    dummy = ListNode(0, head)
    prev = dummy
    for _ in range(left - 1):
        prev = prev.next                     # prev: the anchor, fixed just before the range

    curr = prev.next   # curr: fixed at the range's ORIGINAL start - it becomes the range's tail
    for _ in range(right - left):
        moved = curr.next                    # pull the node right after curr...
        curr.next = moved.next
        moved.next = prev.next               # ...and insert it right after the anchor
        prev.next = moved
    return dummy.next

Where you'll see it

Processing a stream in fixed-size batches works the same way: measure a full batch, act on it as a whole, and hold back a partial last batch. A buffer that flushes only full pages does exactly this. The subrange version is like editing one known section of a document in place.

Which tool for which job?

Common mistakes

Check yourself

Try to answer before opening each one - recalling beats re-reading.

1. Why count k nodes before reversing anything?

2. After a group is reversed, why must its old head be linked to the next group?

3. In subrange reversal, why does curr never move?

Key takeaways

• Count k nodes before reversing a group, so a short last group is a simple early return.
• A reversed group's old head is its new tail. Link it to the next group's new head.
• To reverse a subrange, keep an anchor before it and keep moving the node after the range's first node to the front.
• In that loop, the range's first node stays fixed; it becomes the tail.
• The two techniques look alike but rewire differently. Copying one's loop into the other gives subtly wrong lists.