[/dsa/leetcode]

86 - Partition List

Saturday, 19 September 2026

<medium> [problem]

Quicksort's partition step lifted out on its own - build two chains by appending, concatenate, and terminate the second one or it loops back into the middle of the list.

{linked list}{two pointers}

Problem

Given the head of a linked list and a value x, partition it so that all nodes with value less than x come before nodes with value greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

Input: head = [1,4,3,2,5,2], x = 3
Output: [1,2,2,4,3,5]

Input: head = [2,1], x = 2
Output: [1,2]

Constraints:

  • The number of nodes is in the range [0, 200]
  • -100 <= Node.val <= 100
  • -200 <= x <= 200

Approach

This is quicksort’s partition() asked as its own problem.

[5a, 5b, 5c, 1, 2]        pivot = 2

j=3: 1 < 2, swap(a[0], a[3])
     [1, 5b, 5c, 5a, 2]            5a 5b 5c  ->  5b 5c 5a
pivot swap
     [1, 2, 5c, 5a, 5b]            ->  5c 5a 5b
class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode ld(0), gd(0);
        ListNode* l = &ld, *r = &gd;
        while(head) {
            if(head->val < x) {
                l->next = head;
                l = l->next;
            } else {
                r->next = head;
                r = r->next;
            }
            head = head->next;
        }
        r->next = nullptr;
        l->next = gd.next;
        return ld.next;
    }
};
  • time: O(n) - one pass, each node appended exactly once
  • space: O(1) - four pointers and two stack-allocated dummies
quantinium © 2026