Skip to main content

64. Partition List

mediumAsked at Plaid

Partition a linked list around a value x. Plaid asks this because partitioning a transaction stream into 'below threshold' and 'above threshold' is the same primitive.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Plaid loops.

  • Glassdoor (2025)— Plaid SWE II OA.
  • LeetCode Discuss (2026)— Plaid list partition.

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.

Constraints

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

Examples

Example 1

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

Example 2

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

Approaches

1. Two-pass collect-and-rebuild

First pass: collect into 'less' and 'greater-equal' arrays. Second pass: rebuild.

Time
O(n)
Space
O(n)
// Allocates new nodes.

Tradeoff: Works but allocates.

2. Two dummy heads

Walk once. Each node goes to one of two sub-lists (less or greater-equal). Concatenate.

Time
O(n)
Space
O(1)
function partition(head, x) {
  const less = { next: null }, ge = { next: null };
  let lt = less, gt = ge;
  for (let n = head; n; n = n.next) {
    if (n.val < x) { lt.next = n; lt = lt.next; }
    else { gt.next = n; gt = gt.next; }
  }
  gt.next = null;
  lt.next = ge.next;
  return less.next;
}

Tradeoff: Two dummy heads simplify the splice. Critical: set gt.next = null before concatenation, otherwise the last greater-equal node still points to a less-than node.

Plaid-specific tips

Plaid grades this on the two-dummy-head trick. Bonus signal: explicitly name gt.next = null as the 'cycle prevention' step. Connect to splitting a transaction stream into 'small-value' and 'large-value' buckets while preserving each bucket's chronological order.

Common mistakes

  • Forgetting gt.next = null — leaves a cycle pointing back into the original list.
  • Using one dummy and trying to splice in-place — much more error-prone.
  • Mutating order within each partition (using >= instead of < flips stability).

Follow-up questions

An interviewer at Plaid may pivot to one of these next:

  • Partition into three buckets (Dutch National Flag for lists).
  • Partition around a moving threshold.
  • Same problem on a doubly-linked list.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why two dummy heads?

Each provides a stable anchor for its sub-list. Concatenation is a single pointer assignment at the end.

Why nullify gt.next?

The last greater-equal node still points to whatever was originally after it in the input. Without nullifying, the result has a dangling cycle.

Practice these live with InterviewChamp.AI

Drill Partition List and other Plaid interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →