Split into two chains and rejoin
Partition a list around a value by sending each node to one of two growing chains, then joining the chains end to end. About 14 minutes.
Two chains, one pass
To put every node smaller than x in front, keep the original order, and not copy anything, deal the nodes into two piles as you walk. Each pile is a chain with its own dummy node and tail.
A node smaller than x goes to the end of the small chain. Every other node goes to the end of the other chain. Because you always append, each chain keeps the order the nodes had in the input.
tail.next = node tail = node tail.next = None
2 is below 4, so it joins the small chain: 2.
Join and cut
After the walk, link the end of the small chain to the first real node of the other chain, which is the dummy's next. Return the small chain's dummy next.
One trap: the last node of the other chain may still point at some node in the input. Set its next to nothing before you finish, or the joined list can circle back on itself.
tail1.next = head2 # glue the second on
Why must the last node of the second chain be cut off before returning?
- AIt may still point at a node already placed, forming a loop
- BTo keep the chain sorted
- CTo free memory
Show the answer
It may still point at a node already placed, forming a loop. Nodes keep their old links until you change them.
Partition list
Given the head of a linked list and a value x, rearrange the list so that every node with a value less than x comes before every node with a value greater than or equal to x. Preserve the original relative order of the nodes within each of the two groups. Return the head.
head = [1, 4, 3, 2, 5, 2], x = 3 → [1, 2, 2, 4, 3, 5]
0 ≤ number of nodes ≤ 5,000 · -1,000,000 ≤ node.val, x ≤ 1,000,000