Sublist & K-Group Reversal

July 2026 · 22 min read

This is where reversal grows up. Real problems rarely reverse the whole list; they reverse a window — positions m to n, or every block of k nodes. The reversal itself you already know from the previous post. The hard part, the part that fails silently in interviews, is the reconnection: four links must be rewritten around every reversed segment, and getting a single one wrong drops half the list or spins a cycle. We will build that machinery once and reuse it for Reverse List II, k-Group, Swap Pairs, and rotations.

The Dummy Head, and Why Every Segment Reversal Wants One

When a reversal can touch the first node, the head pointer itself may change — and a changing head is the classic source of a special case. A dummy (sentinel) node placed before the real head converts “the head might change” into “some node’s next might change,” which is uniform and needs no branch.

ListNode dummy(0);
dummy.next = head;
// ... do all the surgery through &dummy ...
return dummy.next;   // the real head, whatever it turned out to be

Every algorithm below starts this way. If you have not met the pattern yet, Sentinels, Dummy Heads & Tail Pointers covers why it removes so many edge cases. Here, treat it as non-negotiable boilerplate.

Reverse Linked List II (positions m..n)

Reverse only the sublist from position m to n (1-indexed), in a single pass. There are two ways, and the difference is instructive.

The detach–reverse–reattach approach walks to m, cuts the sublist free, reverses it with the three-pointer loop, then splices it back. It works, but you juggle four dangling ends at once and it is easy to reverse the wrong count or reattach backwards.

The head-insertion approach is cleaner and genuinely one-pass. Find the node just before position m, then repeatedly take the node after the segment’s first node and “pull it to the front” of the segment. Each pull moves exactly one node forward; after n − m pulls the segment is reversed, with no separate reversal phase and every boundary link written exactly once.

Name the four boundary pointers and never lose track of them:

• prev_seg — the node immediately before position m. It never moves.
• seg_head — the node at position m. It stays physically put and becomes the tail of the reversed segment; its successors get pulled in front of it one by one.
• cur — the node being pulled to the front this iteration (always seg_head->next).
• next — cur->next, saved before any relink.

ListNode* reverseBetween(ListNode* head, int m, int n) {
    ListNode dummy(0);
    dummy.next = head;
    ListNode* prev_seg = &dummy;
    for (int i = 1; i < m; ++i) prev_seg = prev_seg->next;  // stop before position m

    ListNode* seg_head = prev_seg->next;   // position m; becomes the segment tail
    ListNode* cur = seg_head->next;        // first node to pull to the front
    for (int i = 0; i < n - m; ++i) {
        seg_head->next = cur->next;        // 1. detach cur from its slot
        cur->next = prev_seg->next;        // 2. cur points at the current front
        prev_seg->next = cur;              // 3. anchor links to cur as the new front
        cur = seg_head->next;             // 4. the next node to pull
    }
    return dummy.next;
}

The three-line body lifts cur out of its place and re-inserts it directly after prev_seg, so the front of the segment advances one node at a time while seg_head stays fixed as the tail. This beats detach–reverse–reattach because there is no second pass and no length to count twice.

Dry run: 1→2→3→4→5, m = 2, n = 4

prev_seg = 1, seg_head = 2, cur = 3. The loop runs n − m = 2 times.

Two pulls, positions 2..4 reversed, result 1→4→3→2→5. Notice seg_head (node 2) never moved — it simply ended up last in the window, still pointing at 5.

Reverse Nodes in k-Group

Now reverse every consecutive block of k nodes. If the final block has fewer than k nodes, leave it as-is (the default of LeetCode 25); reversing it too is a common follow-up we cover at the end. The one discipline that makes this safe:

The iterative version threads a group_prev anchor from group to group:

ListNode* reverseKGroup(ListNode* head, int k) {
    ListNode dummy(0);
    dummy.next = head;
    ListNode* group_prev = &dummy;

    while (true) {
        // 1. verify k nodes remain; kth is the last node of this group
        ListNode* kth = group_prev;
        for (int i = 0; i < k && kth; ++i) kth = kth->next;
        if (!kth) break;                       // fewer than k -> leave the remainder

        ListNode* group_next = kth->next;      // first node AFTER the group

        // 2. reverse [group_prev->next .. kth], seeding prev with group_next
        ListNode* prev = group_next;
        ListNode* cur = group_prev->next;
        while (cur != group_next) {
            ListNode* next = cur->next;
            cur->next = prev;
            prev = cur;
            cur = next;
        }

        // 3. reconnect and advance the anchor
        ListNode* new_group_prev = group_prev->next;  // old first node, now the tail
        group_prev->next = kth;                        // anchor -> new front
        group_prev = new_group_prev;                   // move anchor to the tail
    }
    return dummy.next;
}

The elegant part is seeding prev = group_next before the inner loop. Because the reversal writes cur->next = prev on the first node it touches, the group’s eventual tail is already wired into the rest of the list — no separate reattachment for the tail. Then group_prev->next = kth wires the anchor to the new front, and new_group_prev (the old first node, now the tail) becomes the next anchor. Each node is reversed exactly once: O(n) time, O(1) extra space.

The recursive formulation

ListNode* reverseKGroup(ListNode* head, int k) {
    ListNode* kth = head;
    for (int i = 0; i < k; ++i) {
        if (!kth) return head;   // fewer than k: leave this block unchanged
        kth = kth->next;
    }
    ListNode* new_head = reverseKGroup(kth, k);   // reverse the REST first
    ListNode* prev = new_head;                    // this group's tail links to it
    ListNode* cur = head;
    for (int i = 0; i < k; ++i) {
        ListNode* next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }
    return prev;   // new front of this group
}

It reads beautifully and is a fine interview answer, but it costs O(n/k) stack frames. For very long lists prefer the iterative loop, exactly as with plain reversal.

Leave the remainder, or reverse it too

The default of LeetCode 25 leaves a trailing block of fewer than k nodes in its original order — that is precisely what if (!kth) break; does in the iterative version and what the if (!kth) return head; base case does in the recursive one. A frequent interview follow-up flips that requirement: reverse the final short block as well. The reassuring part is that the inner three-pointer reversal never changes; only the guard that decides how many nodes to take does. Count how many nodes actually remain, then reverse that many:

// Variant: reverse the trailing block even when it is shorter than k.
int remaining = 0;
for (ListNode* t = group_prev->next; t; t = t->next) ++remaining;
int take = (remaining < k) ? remaining : k;
if (take < 2) break;          // 0 or 1 node left: nothing to reverse
// ... reverse `take` nodes here instead of exactly k, using the same loop ...

The distinction generalises into a rule of thumb: the group-boundary logic is a dial you turn — leave the remainder, reverse it, or skip alternate groups entirely — while the reversal at the core stays the identical primitive from the previous post. Once you internalise that separation, every one of these problems reduces to “where are my four boundary links, and how many nodes does this group take?”

Watch the iterative version run on eight nodes with k = 3. The group_prev and group_next anchors mark the boundaries of each group as it flips; the trailing two nodes are left untouched because they do not fill a group.

Swap Nodes in Pairs (the k = 2 special case)

LeetCode 24 is exactly k-Group with k = 2, and it is worth writing by hand to cement the relinking pattern. Swap by rewiring pointers, not by copying values:

ListNode* swapPairs(ListNode* head) {
    ListNode dummy(0);
    dummy.next = head;
    ListNode* prev = &dummy;
    while (prev->next && prev->next->next) {
        ListNode* a = prev->next;
        ListNode* b = a->next;
        a->next = b->next;   // a jumps past b
        b->next = a;         // b moves in front of a
        prev->next = b;      // anchor to the new front
        prev = a;            // a is now the second node of the pair
    }
    return dummy.next;
}

You can instead write std::swap(a->val, b->val) in a plain walk — a legitimate one-liner, but only when the problem does not forbid modifying values and the payload is cheap to copy. The moment nodes carry identity (they are shared, hold extra fields, or the grader checks node addresses), value-swapping is wrong and relinking is the only correct answer. Default to relinking; it always works.

Extensions: Rotate a Sublist, Reverse Alternate k Nodes

Both are compositions of the primitives above, which is the point — once the reconnection discipline is solid, variations are cheap.

• Rotate a sublist right by r. Within window [m, n], detach the sublist using the same prev_seg/group_next boundary pointers, find the new head r nodes from the sublist’s end, relink the sublist’s old tail to its old head, cut after the new head, and splice the rotated piece back between the boundaries.
• Reverse alternate k nodes. Reverse the first k, then skip the next k without reversing, then reverse the next k, and so on. It is the k-group loop with a toggle: after reversing a group, walk k nodes forward, moving group_prev to the last skipped node before the next reversal.

Complexity

The Reconnection Checklist

Miss link 1 and you drop the entire prefix; miss link 2 and you drop the suffix or spin a cycle; miss the anchor advance in link 4 and you reverse the same group forever. When a segment-reversal solution “loses half the list,” the bug is always one of these four.

Check Yourself

Six scenarios from the boundary bookkeeping. Pick the true statement.

Practice

• LeetCode 92 — Reverse Linked List II head insertion the canonical one-pass sublist reversal with a dummy head.
• LeetCode 25 — Reverse Nodes in k-Group check-then-reverse confirm k nodes exist before touching any pointer.
• LeetCode 24 — Swap Nodes in Pairs relink the k = 2 case done by rewiring, not value swapping.
• LeetCode 61 — Rotate List boundary pointers close the list into a ring, then cut at the new tail.
• LeetCode 206 — Reverse Linked List primitive the whole-list base case every segment reversal is built on.
• LeetCode 143 — Reorder List compose split, reverse the tail, then interleave the halves.