DSA · Linked List · #134
Partition List
Module 42 · difficulty 3/5·⏱ 30:00starts on first keystroke
Given the `head` of a singly linked list and a value `x`, partition the list so that all nodes with value **less than** `x` come before all nodes with value **greater than or equal to** `x`. You must preserve the original **relative order** of the nodes within each of the two partitions. Implement `partition(head, x)`. List nodes have the shape `{ val, next }`; return the head of the modified list.
Examples
head = [1,4,3,2,5,2], x = 3→[1,2,2,4,3,5]— Nodes < 3 (1,2,2) keep their order, then nodes >= 3 (4,3,5) keep theirs.head = [2,1], x = 2→[1,2]head = [], x = 0→[]
Constraints
- · The number of nodes is in the range [0, 200].
- · -100 <= Node.val <= 100
- · -200 <= x <= 200
Session phases
A · Clarify
B · Approach
C · Complexity
D · Edges
E · Code
F · Tradeoff
G · Score
Phase A — Clarify
Ask questions about input bounds, types, and edge constraints.
Ask the coach clarifying questions about the problem.
When you've covered this phase, advance to the next.