Why it works
- Each node goes to the end of its list, in the order the old list gives them, so both groups keep their order.
- The two dummies mean an empty list needs no check: with no node under x, lessHead.next simply becomes the first node of the other list.
- Nodes are moved, not copied, so the last node of the more list keeps its old next. more.next = none cuts it before the lists are joined; without that the answer loops.
Complexity
Time O(n): one pass, each node is moved once. Memory O(1): the nodes are reused, only the two dummies are new.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗