Skip to main content

67. Partition List

mediumAsked at Snowflake

Partition a linked list around a value x so that nodes < x come before nodes >= x, preserving relative order. Snowflake asks this to test two-builder pattern — same shape as range-repartition during shuffle.

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

Source citations

Public interview reports confirming this problem appears in Snowflake loops.

  • Glassdoor (2025-Q4)— Snowflake execution-engine team uses this to discuss range partitioning.
  • LeetCode Discuss (2025-08)— Reported at Snowflake SDE-I screens.

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 into two arrays, rebuild

Walk; push < x to left[], >= x to right[]; rebuild a new list.

Time
O(n)
Space
O(n)
// outline: build two arrays then chain them.

Tradeoff: Works but allocates extra arrays.

2. Two dummy builders (optimal)

Two dummy heads (lessHead, geHead) and two tails. Walk; append to lessTail if val < x, else geTail. Stitch lessTail.next = geHead.next; geTail.next = null.

Time
O(n)
Space
O(1)
function partition(head, x) {
  const lessHead = { val: 0, next: null };
  const geHead = { val: 0, next: null };
  let lessTail = lessHead, geTail = geHead;
  let curr = head;
  while (curr) {
    if (curr.val < x) { lessTail.next = curr; lessTail = curr; }
    else { geTail.next = curr; geTail = curr; }
    curr = curr.next;
  }
  geTail.next = null;
  lessTail.next = geHead.next;
  return lessHead.next;
}

Tradeoff: Single pass, in-place pointer manipulation. The two-builder pattern is the same as range repartitioning during shuffle.

Snowflake-specific tips

Snowflake interviewers want the two-builder pattern. Bonus signal: connect to range repartitioning — when redistributing rows by value range, each compute node maintains a builder per output range. The shape is identical.

Common mistakes

  • Forgetting to null-terminate geTail.next — creates a cycle if the original tail's next was within geTail.
  • Mixing up which builder gets the < x values.
  • Using two arrays instead of in-place splicing — works but uses extra memory.

Follow-up questions

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

  • Stable QuickSort partition.
  • k-way partition for range repartitioning.
  • How does Snowflake redistribute rows across compute nodes?

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 null-terminate geTail?

Without it, geTail.next still points to wherever it pointed in the original list — could be inside the < x partition. Null termination ends the list cleanly.

How does this map to range repartitioning?

When shuffling rows by a hash or range key, each output partition has its own buffer. Rows are appended to the buffer matching their key — exactly this two-builder pattern, scaled to k builders.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →