The problem
Rearrange a linked list so all nodes less than x come before nodes ≥ x, keeping the original order within each group.
Input: 1 → 4 → 3 → 2 → 5 → 2, x = 3 Output: 1 → 2 → 2 → 4 → 3 → 5
Picture it
Picture coaches arriving at a junction with two sidings. Coaches under x go to the first siding, the rest to the second, each in arrival order. At the end, the first siding is coupled to the front of the second.
Short version: the full lesson (brute force, complexity, edge cases and a quiz) is still being written. The animation is complete.
The key idea
Two dummy-headed lists, then join them. O(n).
Python solution
def partition(head, x):
small = s = Node(0)
big = b = Node(0)
while head:
if head.val < x:
s.next = head; s = s.next
else:
b.next = head; b = b.next
head = head.next
b.next = None
s.next = big.next
return small.nextIn the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.