How would you merge two sorted singly linked lists into a single sorted list?

• A. Attach the lists end-to-end without comparing values.
• B. Use a dummy head; repeatedly attach the smaller node and advance that list; append remainder at end.
• C. Attach all nodes from the second list to the end of the first list.
• D. Sort each list, then concatenate.

Answer: (B)

Merging two sorted lists is about building a single sorted sequence by always taking the smaller current node from the fronts of the two lists. Using a dummy head simplifies the process because it removes the need to handle the first node as a special case; you can just attach nodes to the tail as you go.

Here's how it works conceptually: keep two pointers at the heads of the lists. Repeatedly compare the values at these two pointers, attach the smaller node to the merged list, and advance that list’s pointer. Move the tail forward each time you attach a node. When one list runs out, simply append the remainder of the other list. This guarantees the merged list is sorted, since at every step you pull the smallest available value and the remaining elements are already in order.

The approach is efficient because it only traverses each list once, giving a time complexity of O(n + m) and O(1) extra space aside from the new list structure you’re building (or, if you reuse nodes in place, no extra space at all).

Why the other ideas don’t work for maintaining order: attaching the lists end-to-end without comparing values can break the required nondecreasing order. Simply concatenating the second list to the end of the first ignores interleaving possibilities where the second list has smaller elements that should come in between. Sorting each list first and then concatenating fails to guarantee a globally sorted result and adds unnecessary work since the two input lists are already sorted.