Merge Two Sorted Lists
FreeLinked listsEasy20 of 75
The problem
Combine two ascending singly linked lists into one ascending list by relinking their nodes. Either input may be empty.
Example
1 → 4 and 2 → 3 become 1 → 2 → 3 → 4
Need a hint?
A dummy head removes the special case for the first output node.
Write pseudocode, trace the example, or note an edge case. This scratchpad does not run code.
Notes stay in this browser when storage is available.
Read the solution approach
Maintain a tail behind a dummy node. Repeatedly attach the smaller input head and advance that input. Advance tail after each attachment. Once one input is exhausted, attach the other remainder and return dummy.next.
Complexity
O(m + n) time and O(1) extra space.
Before moving on, explain why the algorithm is correct and trace a boundary case without looking at the approach.