Merge Two Sorted Lists — Blind 75 practice

Problem

You are given the heads of two sorted linked lists. Splice them into one sorted list — reusing the existing nodes, not copying values — and return its head.

Examples

Example 1:
Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

Example 2:
Input: list1 = [], list2 = []
Output: []

Example 3:
Input: list1 = [], list2 = [0]
Output: [0]

Example 4:
Input: list1 = [5], list2 = [1,2]
Output: [1,2,5]

Constraints

0 <= each list's length <= 50
-100 <= Node.val <= 100
Both lists are sorted ascending.

Prerequisites

Linked lists — a node holds a value and a next reference, and rearranging a list means moving references, never values.
Dummy heads: a node in front of the list so the first element stops being a special case.
Two pointers on a list — one ahead of the other, or one moving twice as fast.

How to think about it

1. Dummy Head and a Tail Pointer Optimal

Intuition

Both lists are sorted, so the smallest remaining node is always at the front of one of them — take it, advance that list, repeat. The awkward part is the very first node, since there is no tail to attach it to yet; a dummy node in front removes that case entirely, and the answer is whatever it ends up pointing at.

Algorithm

1. Make a dummy node and let tail point at it.
2. While both lists have nodes, attach the smaller front and advance that list.
3. Attach whichever list still has nodes — it is already sorted and already larger.
4. Return dummy.next.

Time & Space

Time O(n + m). Space O(1): the nodes are spliced, not copied.