Skip to main content

67. Partition List

mediumAsked at Ola

Partition a linked list around a value, preserving relative order.

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

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

  • Number of nodes is in [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 passes with array

Collect values, partition into two lists, rebuild.

Time
O(n)
Space
O(n)
const low=[], high=[]; let n = head;
while (n) { (n.val<x?low:high).push(n.val); n=n.next; }
// rebuild list from low.concat(high)

Tradeoff:

2. Two dummies

Build a less-than chain and a >= chain with dummy heads; concatenate them.

Time
O(n)
Space
O(1)
function partition(head, x) {
  const less = { next: null }, gte = { next: null };
  let lp = less, gp = gte;
  while (head) {
    if (head.val < x) { lp.next = head; lp = head; }
    else { gp.next = head; gp = head; }
    head = head.next;
  }
  gp.next = null;
  lp.next = gte.next;
  return less.next;
}

Tradeoff:

Ola-specific tips

Ola interviewers want to see the two-chain pattern; tie it to splitting active rides above/below a fare-cap threshold without losing chronology.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →