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

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.

// Java quick-and-dirty
ListNode lessHead = new ListNode(0), moreHead = new ListNode(0);
ListNode less = lessHead, more = moreHead;
while (head != null) {
    if (head.val < x) less = less.next = head;
    else more = more.next = head;
    head = head.next;
}
less.next = moreHead.next;
more.next = null;
return lessHead.next;

🧠 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

• Create two dummy list heads:
  • Why dummy nodes? So your future self doesn’t curse you over null checks.

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

• Set up trailing pointers:
  • Use less for the light crowd, more for everyone else.

  ListNode less = lessHead, more = moreHead;

• Walk the list once:
  • Decision time: Bouncer, send each node to its designated queue.

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

• Stitch and finish:
  • Connect the lightweight queue to the heavyweight, and don’t forget to cut the loop at the end.

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

• Return new head:
  • The dummy node’s next is the start of your brave new partitioned world.

  return lessHead.next;

💻 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.

🧠 Interviewer Brain-Tattoo

If you wouldn’t randomly swap people in a boarding queue, don’t do it with nodes. Dummy nodes: because drama belongs in airport lines, not your code.