Loading problem…
You are given the heads of two sorted linked lists list1 and list2. Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists. Return the head of the merged linked list.
Example 1
Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]
Explanation: Repeatedly take the smaller front node: 1 (list1), 1 (list2), 2, 3, 4, 4. The result is [1,1,2,3,4,4].
Example 2
Input: list1 = [], list2 = []
Output: []
Explanation: Both lists are empty, so the merged list is empty.
Example 3
Input: list1 = [], list2 = [0]
Output: [0]
Explanation: list1 is empty, so the result is just list2: [0].
Walk both lists in parallel and at each step splice the smaller of the two heads onto the result. A *dummy* node sitting before the real start of the result list lets us always say `tail.next = X` without a special case for the very first node.
Run checks all cases above. Submit evaluates all test cases.