Merge Two Sorted Lists

Q: What is the dummy node for?

Without it, the first node of the result has to be chosen separately before the loop. The dummy gives tail something to start from, and you return dummy.next at the end.

Q: Is the recursive version acceptable?

Yes: return the smaller head after setting its next to the merge of the rest. It is short, but it uses one stack frame per node, so long lists can overflow the stack.

Q: Where does this appear in infra work?

Merging two time-sorted log streams, for example from two replicas of a service, into one ordered timeline is exactly this merge. sort -m in coreutils does it on already-sorted files without re-sorting.

easyLinked list Must-do

You get the heads of two singly linked lists, list1 and list2. Each list is already sorted in non-decreasing order. Combine them into one sorted linked list by linking the existing nodes together, and return the head of the combined list.

Either list, or both, may be empty.

Examples

Example 1

Input: list1 = 2 -> 5 -> 9 list2 = 3 -> 4 -> 10 -> 12

Output: 2 -> 3 -> 4 -> 5 -> 9 -> 10 -> 12

Example 2

Input: list1 = (empty) list2 = 6 -> 7

Output: 6 -> 7

Explanation: When one list is empty, the answer is simply the other list.

Hints

Approach

This is the merge step of merge sort, done by relinking nodes.

Create a dummy node and a tail pointer to it. The merged list will hang off dummy.next.
While both lists have nodes, attach the one with the smaller value to tail.next, advance that list, and advance tail.
When one list is empty, the other is already sorted, so attach it in one step.
Return dummy.next.

Using <= on ties takes from list1 first, which keeps equal values in their original relative order (a stable merge).

ComplexityTime O(m + n)Space O(1)

Python

# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
 
class Solution:
    def mergeTwoLists(self, list1: ListNode | None, list2: ListNode | None) -> ListNode | None:
        dummy = ListNode()        # placeholder so the head needs no special case
        tail = dummy
        while list1 and list2:
            if list1.val <= list2.val:
                tail.next, list1 = list1, list1.next
            else:
                tail.next, list2 = list2, list2.next
            tail = tail.next
        tail.next = list1 or list2   # attach whatever is left
        return dummy.next

Follow-up questions

Merge k sorted lists instead of two (use a min-heap of list heads).
Remove duplicates while merging, so each value appears once.

Frequently asked questions

Without it, the first node of the result has to be chosen separately before the loop. The dummy gives tail something to start from, and you return dummy.next at the end.

Yes: return the smaller head after setting its next to the merge of the rest. It is short, but it uses one stack frame per node, so long lists can overflow the stack.

Merging two time-sorted log streams, for example from two replicas of a service, into one ordered timeline is exactly this merge. sort -m in coreutils does it on already-sorted files without re-sorting.

Problem statement