Medium · Two Dummy Lists
Understand → Visualise → Practice.
Re-link nodes so values below pivot precede the rest while preserving relative order in both groups.
Walk the list once, appending each node to a 'less than pivot' list or a 'the rest' list, both with dummy heads. Joining them keeps each group in its original order.
One for nodes below the pivot, one for the others.
Append each node to the tail of the matching list.
Link the first list's tail to the second list's first real node, and end the second list with null.
O(n) time and O(1) extra space.
Forgetting to set the second list's tail to null can leave a cycle from the old links.
Read the full guide first: Linked Lists.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.