Partitioning, Reordering & Rotation

July 2026 · 22 min read

A surprising number of "medium" linked-list problems are the same problem wearing different clothes: build one or more new lists by relinking existing nodes, then stitch them back together. Once you see the meta-pattern — separate, then join — partition, odd-even split, reorder, and rotation all collapse into a few lines each. This post walks the whole family, and dwells on the two ways every one of them breaks: forgetting to terminate a tail (which creates a cycle) and forgetting to save a head before you overwrite it.

The "Build Two Lists and Stitch" Pattern

The core move never changes. You keep one or more dummy heads, each with a tail cursor. You walk the input once, and for each node you decide which output it belongs to and append it there in O(1). At the end you connect the outputs and — this is the part people skip — you null-terminate the final tail, because the last node you appended still points wherever it happened to point in the original list.

ListNode lessD(0), grtrD(0);          // two dummy heads
ListNode *lt = &lessD, *gt = &grtrD;  // two tail cursors
for (ListNode* cur = head; cur; cur = cur->next) {
    if (predicate(cur)) lt = lt->next = cur;   // append to "less"
    else                gt = gt->next = cur;   // append to "greater"
}
gt->next = nullptr;                   // TERMINATE, or you will build a cycle
lt->next = grtrD.next;                // stitch: less-tail -> greater-head

Everything below is a variation on those eight lines. The dummy head removes the "is this the first node?" branch; the tail cursor makes every append O(1); and the termination step is the invariant you must never drop.

Two invariants recur through every problem in this post, and naming them now saves you debugging later. First, append at the tail, never prepend: pushing each node onto the end of its bucket preserves the input order, which is exactly what stability-preserving rearrangements like Partition and Odd–Even require — prepend instead and you silently reverse each group. Second, whatever ends a chain must be null-terminated, and whatever a chain starts from must be saved before a cursor marches past it. Almost every bug below is a violation of one of those two rules: a tail left pointing into old nodes (a cycle), or a head lost because you advanced without stashing it first.

Partition List (LeetCode 86)

Given a value x, reorder the list so that every node with value < x comes before every node with value ≥ x, preserving the original relative order within each group. That "preserving order" clause is why you build two lists instead of swapping in place.

ListNode* partition(ListNode* head, int x) {
    ListNode lessD(0), grtrD(0);
    ListNode *lt = &lessD, *gt = &grtrD;
    for (ListNode* cur = head; cur; cur = cur->next) {
        if (cur->val < x) lt = lt->next = cur;
        else              gt = gt->next = cur;
    }
    gt->next = nullptr;         // <-- without this line: an infinite cycle
    lt->next = grtrD.next;      // less-tail points at greater-head
    return lessD.next;
}

One pass, O(n) time, O(1) extra space. The two dummy heads are stack objects, not allocations.

Odd Even Linked List (LeetCode 328)

Group all nodes at odd positions together, followed by all nodes at even positions — by index, not by value. Same shape as partition, but here the elegance is that you can weave two cursors through the original list without a second dummy, as long as you save the even head so you can reattach it at the end.

ListNode* oddEvenList(ListNode* head) {
    if (!head || !head->next) return head;
    ListNode* odd  = head;              // 1st, 3rd, 5th, ...
    ListNode* even = head->next;        // 2nd, 4th, 6th, ...
    ListNode* evenHead = even;          // <-- SAVE it; we overwrite even below
    while (even && even->next) {
        odd->next  = even->next;        // odd skips the even node
        odd        = odd->next;
        even->next = odd->next;         // even skips the odd node
        even       = even->next;
    }
    odd->next = evenHead;               // reconnect the two chains
    return head;
}

If you do not stash evenHead before the loop, the loop marches even to the end and you have no way to find where the even chain began. Saving a head before you advance past it is the second recurring discipline of this whole topic. O(n) time, O(1) space.

Reorder List (LeetCode 143)

Reorder L0→L1→...→Ln into L0→Ln→L1→Ln-1→.... This is the single best example in the whole series of composing primitives you already own. It is exactly three phases, each of which is a standalone algorithm from earlier posts:

1. Find the middle with fast/slow pointers.
2. Reverse the second half with the standard three-pointer reversal.
3. Weave the two halves alternately.

void reorderList(ListNode* head) {
    if (!head || !head->next) return;

    // Phase 1: find the middle (slow ends at the last node of the first half)
    ListNode *slow = head, *fast = head;
    while (fast->next && fast->next->next) {
        slow = slow->next;
        fast = fast->next->next;
    }

    // Phase 2: reverse the second half
    ListNode* second = slow->next;
    slow->next = nullptr;               // cut into two halves
    ListNode* prev = nullptr;
    while (second) {
        ListNode* nxt = second->next;
        second->next = prev;
        prev = second;
        second = nxt;
    }

    // Phase 3: weave first and reversed-second alternately
    ListNode* first = head;
    second = prev;                      // head of the reversed second half
    while (second) {
        ListNode* f = first->next;
        ListNode* s = second->next;
        first->next = second;
        second->next = f;
        first = f;
        second = s;
    }
}

Notice that no phase invents anything new: finding the middle is the fast/slow pointer post, reversal is the reversal post, and the weave is the same "save both nexts, then relink" surgery from traversal patterns. That is the lesson — hard list problems are usually two or three easy ones stacked.

Dry run: reorder 1→2→3→4→5

Rotate Right by k (LeetCode 61)

Rotate the list to the right by k places. The clean trick is to close the list into a ring, then cut it at the right spot. The new head is k nodes from the end, i.e. the node n - k steps from the old head.

ListNode* rotateRight(ListNode* head, int k) {
    if (!head || !head->next || k == 0) return head;

    // 1. length + tail
    int n = 1;
    ListNode* tail = head;
    while (tail->next) { tail = tail->next; ++n; }

    // 2. close into a ring
    tail->next = head;

    // 3. reduce k, then walk to the new tail
    k %= n;                             // <-- the modulo that makes large k O(n)
    int stepsToNewTail = n - k;
    ListNode* newTail = head;
    for (int i = 1; i < stepsToNewTail; ++i) newTail = newTail->next;

    ListNode* newHead = newTail->next;
    newTail->next = nullptr;            // reopen the ring
    return newHead;
}

Remove Duplicates from a Sorted List (83 and 82)

On a sorted list, duplicates are adjacent, so one pass suffices. The two variants differ in whether you keep one copy or delete every copy of a repeated value.

83 — keep one. No dummy needed, because the first occurrence always survives, so head never changes.

ListNode* deleteDuplicates(ListNode* head) {
    ListNode* cur = head;
    while (cur && cur->next) {
        if (cur->next->val == cur->val) {
            ListNode* dup = cur->next;
            cur->next = dup->next;      // unlink one duplicate
            delete dup;                // real code frees; LeetCode judges leak
        } else {
            cur = cur->next;           // only advance when NOT deleting
        }
    }
    return head;
}

82 — remove all copies. Now the head itself can vanish (if it starts a run), so you need a dummy. And you need a prev that stays behind the run plus an inner loop that peeks ahead while values are equal.

ListNode* deleteDuplicatesII(ListNode* head) {
    ListNode dummy(0);
    dummy.next = head;
    ListNode* prev = &dummy;           // last node known to be unique
    ListNode* cur = head;
    while (cur) {
        if (cur->next && cur->next->val == cur->val) {
            int v = cur->val;
            while (cur && cur->val == v) {   // skip the ENTIRE run of v
                ListNode* dead = cur;
                cur = cur->next;
                delete dead;
            }
            prev->next = cur;          // prev leaps over the whole run
        } else {
            prev = cur;
            cur = cur->next;
        }
    }
    return dummy.next;
}

Why the naive one-pointer version drops a node here: with only a single forward cursor you can express "unlink the node in front of me" but not "unlink myself and keep my predecessor linked to what follows me". When a run starts at the node your single pointer sits on, you have no handle on the node before it, so either the first copy of the run survives (you solved 83 by accident) or the link from the previous unique node dangles. The dummy-plus-prev is precisely the handle that lets you delete a whole run including its first element and re-anchor the list. Both variants are O(n) time, O(1) space.

Remove Duplicates from an Unsorted List

Without sorting, equal values are not adjacent, so you trade space against time. The hash-set version is O(n) time and O(n) space; the two-pointer version is O(n²) time and O(1) space — the classic "no buffer allowed" interview follow-up.

// O(n) time, O(n) space
ListNode* removeDupsHashed(ListNode* head) {
    std::unordered_set<int> seen;
    ListNode dummy(0);
    dummy.next = head;
    ListNode* prev = &dummy;
    for (ListNode* cur = head; cur; cur = cur->next) {
        if (seen.count(cur->val)) prev->next = cur->next;   // skip seen value
        else { seen.insert(cur->val); prev = cur; }
    }
    return dummy.next;
}

// O(n^2) time, O(1) space
void removeDupsNoBuffer(ListNode* head) {
    for (ListNode* cur = head; cur; cur = cur->next) {
        ListNode* runner = cur;
        while (runner->next) {
            if (runner->next->val == cur->val)
                runner->next = runner->next->next;    // drop later duplicate
            else
                runner = runner->next;
        }
    }
}

Swapping Nodes: Relink vs. Value Swap (24 and 1721)

There are two ways to "swap" in a list, and knowing which is legitimate is the whole point.

Swap Nodes in Pairs (24) asks you to swap adjacent nodes. The intended solution relinks pointers, because the exercise is about pointer surgery:

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 in front of a
        prev->next = b;      // predecessor points at the new front
        prev = a;            // advance two nodes
    }
    return dummy.next;
}

Swapping Nodes in a Linked List (1721) asks you to swap the values at the k-th node from the front and the k-th from the end. Because only values need to end up swapped and no external code holds node identities, a value swap is perfectly acceptable and far simpler:

ListNode* swapNodes(ListNode* head, int k) {
    ListNode* first = head;
    for (int i = 1; i < k; ++i) first = first->next;   // k-th from front
    ListNode* second = head;
    for (ListNode* p = first->next; p; p = p->next)     // gap of k-1 => k-th from end
        second = second->next;
    std::swap(first->val, second->val);
    return head;
}

Complexity Summary

Check Yourself

Each item gives a situation; pick the statement that is actually true.

Practice

• LeetCode 86 — Partition List two lists the canonical stitch; remember to null-terminate.
• LeetCode 328 — Odd Even Linked List weave save the even head before the loop.
• LeetCode 143 — Reorder List compose middle + reverse + weave in one function.
• LeetCode 61 — Rotate List ring close the loop, reduce k, cut once.
• LeetCode 82 — Remove Duplicates from Sorted List II dummy delete whole runs with a lagging prev.
• LeetCode 24 — Swap Nodes in Pairs relink pointer surgery, not a value swap.