Partition a Linked List Around a Pivot

medium linked list two pointers

Problem

Given a linked list and a pivot value x, reorder the list so every node with value < x comes before every node with value ≥ x. Within each group the original relative order must be preserved.

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;
}

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