Easy · Dummy Head
Understand → Visualise → Practice.
Merging is the heart of merge sort. With linked lists you can merge by relinking nodes, without copying values.
Start from a dummy node so the first real node isn't a special case. Repeatedly attach the smaller of the two heads.
tail = dummy.
tail.next = smaller; advance that list and tail.
When one list ends, link the other on.
O(n + m) time, O(1) extra space.
Return dummy.next, not dummy.
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.