Linked lists make splicing cheap: re-pointing a single next reference moves an entire tail from one list to another. Merging two sorted lists is the classic example, and it is also the heart of merge sort.
Given the heads of two sorted singly linked lists l1 and l2, merge them into one sorted list by re-linking the existing nodes, and return the head of the merged list.
Examples
Input: l1 = 1 -> 2 -> 4, l2 = 1 -> 3 -> 4
Output: 1 -> 1 -> 2 -> 3 -> 4 -> 4
Input: l1 = (empty), l2 = 0
Output: 0
Constraints
0 <= number of nodes in each list <= 500- Both input lists are sorted in non-decreasing order
Goals
- Use a dummy head node to avoid special-casing the first element
- Splice nodes from two lists into one by re-linking next references
- Attach the leftover tail once one list runs out