MediumPro challengePythonJavaScriptTypeScript
Linked List — Partition List
Data StructuresLinked ListTwo Pointers
solve(values, x) builds a singly linked list and partitions it so that every node with
a value less than `x` comes before every node with a value **greater than or equal
to x. The relative order inside each group must be preserved** (the partition is
stable). Return the values.
Build two chains while walking the list once — a "small" chain and a "large" chain, each
behind its own dummy head — then link the end of the small chain to the start of the large
one. Remember to terminate the large chain with null, or you may leave a cycle.
Examples
solve([1,4,3,2,5,2], 3) → [1,2,2,4,3,5]
solve([2,1], 2) → [1,2]
solve([5,4,3], 1) → [5,4,3]Sample tests
Test #1Classic example
Input: [[1,4,3,2,5,2],3]
Output: [1,2,2,4,3,5]
Test #2Two nodes
Input: [[2,1],2]
Output: [1,2]
Test #3Nothing is smaller
Input: [[5,4,3],1]
Output: [5,4,3]