Skip to main content

63. Partition List

mediumAsked at Vercel

Partition a linked list around a pivot value while preserving relative order. Vercel asks this for the two-list splice pattern — same shape as their stable bucket-sort for priority-queued edge requests.

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

Source citations

Public interview reports confirming this problem appears in Vercel loops.

  • Glassdoor (2025-12)— Vercel platform onsite; two-list splice expected.
  • LeetCode Discuss (2026-Q1)— Listed in Vercel screen pool.

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. Collect to array, partition, rebuild

Dump values, partition stably, rebuild a new list.

Time
O(n)
Space
O(n)
function partition(head, x) {
  const less = [], greater = [];
  for (let c = head; c; c = c.next) (c.val < x ? less : greater).push(c.val);
  const dummy = { next: null };
  let tail = dummy;
  for (const v of [...less, ...greater]) { tail.next = { val: v, next: null }; tail = tail.next; }
  return dummy.next;
}

Tradeoff: Allocates new nodes. Vercel will ask for in-place.

2. Two dummy lists, splice (optimal)

Build two lists in parallel: less and greater. Walk original; attach each node to the correct tail. At the end, link less.tail -> greater.head and null-terminate.

Time
O(n)
Space
O(1)
function partition(head, x) {
  const lessDummy = { next: null };
  const greaterDummy = { next: null };
  let lt = lessDummy, gt = greaterDummy;
  for (let cur = head; cur; cur = cur.next) {
    if (cur.val < x) { lt.next = cur; lt = cur; }
    else { gt.next = cur; gt = cur; }
  }
  gt.next = null; // critical: terminate greater list
  lt.next = greaterDummy.next;
  return lessDummy.next;
}

Tradeoff: In-place. The gt.next = null at the end is essential — without it, the last greater node still points at some old next, creating a cycle.

Vercel-specific tips

Vercel grades the two-dummy splice. Bonus signal: the gt.next = null termination (most common bug to forget) and stating that 'stable partition' = relative order preserved within each group, which this approach gives for free.

Common mistakes

  • Forgetting to null-terminate the greater list — produces a cycle.
  • Splicing lt.next = greaterDummy without .next — links to the dummy itself.
  • Modifying val instead of pointers — the problem allows either, but pointer-only is the canonical answer.

Follow-up questions

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

  • Sort List (LC 148) — merge sort on a linked list.
  • Partition list in-place WITHOUT relative-order preservation (Lomuto-style).
  • Three-way partition (Dutch National Flag on a 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 dummies?

They let you splice nodes onto either list without special-casing the first node of each. After the loop, link less.tail -> greater.head.

Why null-terminate greater?

Because we reused the original nodes, their .next pointers still hold their old positions in the input. The last greater node's old next is whatever followed it in the input — possibly a less-than node. Setting it to null cuts that loop.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →