Partition List

medium linked list two pointers

Problem

Given the head of a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x. You should preserve the original relative order of the nodes in each of the two partitions.

Build two separate sublists with their own dummy heads — a "less" list and a "greater-or-equal" list. Walk the original list once, append each node to the matching sublist; at the end, splice the two together.

Input1 → 4 → 3 → 2 → 5 → 2, x = 3

Output1 → 2 → 2 → 4 → 3 → 5

list (comma-separated)

pivot x

def partition(head, x):
    less = ListNode(); ge = ListNode()
    lt, gt = less, ge
    while head:
        if head.val < x:
            lt.next = head; lt = lt.next
        else:
            gt.next = head; gt = gt.next
        head = head.next
    gt.next = None
    lt.next = ge.next
    return less.next

function partition(head, x) {
  const less = { next: null }, ge = { next: null };
  let lt = less, gt = ge;
  while (head) {
    if (head.val < x) { lt.next = head; lt = lt.next; }
    else              { gt.next = head; gt = gt.next; }
    head = head.next;
  }
  gt.next = null;
  lt.next = ge.next;
  return less.next;
}

class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode less = new ListNode(), ge = new ListNode();
        ListNode lt = less, gt = ge;
        while (head != null) {
            if (head.val < x) { lt.next = head; lt = lt.next; }
            else              { gt.next = head; gt = gt.next; }
            head = head.next;
        }
        gt.next = null;
        lt.next = ge.next;
        return less.next;
    }
}

ListNode* partition(ListNode* head, int x) {
    ListNode less, ge;
    ListNode *lt = &less, *gt = &ge;
    while (head) {
        if (head->val < x) { lt->next = head; lt = lt->next; }
        else                { gt->next = head; gt = gt->next; }
        head = head->next;
    }
    gt->next = nullptr;
    lt->next = ge.next;
    return less.next;
}

Explanation

We want every node smaller than x to come before every node that is x or larger, while keeping the original order inside each group. The clean way is to build two separate sublists and then join them.

We make two chains, each with its own dummy head: a less list (values below x) and a ge list (values at or above x), tracked by tails lt and gt. Walking the original list once, we append each node to whichever chain it belongs to.

Order is preserved automatically because we always append to the tail, so nodes stay in the sequence we met them. At the end we cut off the ge list with gt.next = None and link lt.next = ge.next to put the less list in front.

Example: 1 → 4 → 3 → 2 → 5 → 2 with x = 3. Less collects 1, 2, 2; ge collects 4, 3, 5. Joined: 1 → 2 → 2 → 4 → 3 → 5.

It is a single pass that only relinks existing nodes, so the extra memory is just the two dummy heads.

Time: O(n) Space: O(1)