The O(n) Club: Partition List—How to Herd Nodes Without Losing Your Mind

⚡ TL;DR

Sort a linked list so that values less than x go before everything else, without messing up their original order? Don’t reach for the aspirin yet—just build two dummy lists as you traverse, stitch them up at the end, and you’re done.

🧠 How Devs Usually Mess This Up

Every time this problem pops up, developers try to reinvent the disaster wheel:

🔍 What’s Actually Going On

Picture yourself as an airport line bouncer. You’ve got two ropes: one line for folks with fewer than 3 carry-ons (the privileged < x), the other for everyone else. You send each traveler to the right line as they arrive, never changing their spot within their line. At the end, you undo the velvet rope and merge the lines, so that the light-packers go through first, still in order, followed by the “overpackers.” If you try shuffling people in the middle, expect airport security (aka your interviewer) to look at you funny.

🛠️ PseudoCode

Why dummy nodes? So your future self doesn’t curse you over null checks.
Use less for the light crowd, more for everyone else.
Decision time: Bouncer, send each node to its designated queue.
Connect the lightweight queue to the heavyweight, and don’t forget to cut the loop at the end.
The dummy node’s next is the start of your brave new partitioned world.

Return new head:

return lessHead.next;

Stitch and finish:

less.next = moreHead.next;
more.next = null;

Walk the list once:

while (head != null) {
    if (head.val < x) less = less.next = head;
    else more = more.next = head;
    head = head.next;
}

Set up trailing pointers:

ListNode less = lessHead, more = moreHead;

Create two dummy list heads:

ListNode lessHead = new ListNode(0);
ListNode moreHead = new ListNode(0);

💻 The Code

// Java - Partition List
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}
 public ListNode partition(ListNode head, int x) {
    ListNode lessHead = new ListNode(0);
    ListNode moreHead = new ListNode(0);
    ListNode less = lessHead, more = moreHead;
    while (head != null) {
        if (head.val < x) {
            less.next = head;
            less = less.next;
        } else {
            more.next = head;
            more = more.next;
        }
        head = head.next;
    }
    less.next = moreHead.next;
    more.next = null;
    return lessHead.next;
}

⚠️ Pitfalls, Traps & Runtime Smacks

If you skip more.next = null: Enjoy debugging a next-pointer cycle at 2am.
Dummy nodes save your bacon: They keep all those annoying edge-cases at bay. One partition empty? Still works. Both empty? Still works. So elegant, even your cat gets it.
Time/Space: O(n) time, O(1) (real) extra space. Quit flexing your Big-O if you can’t remember to de-loop lists.