Problem
You are given the heads of two linked lists, each sorted in non-decreasing order. Splice their nodes together into one sorted list and return its head, reusing the existing nodes.
Worked examples
Input: list1 = [1,3,8], list2 = [2,3,4]
Output: [1,2,3,3,4,8]
Input: list1 = [], list2 = [0]
Output: [0]
Hints
Hint 1
Repeatedly take the smaller of the two current heads.
Hint 2
A dummy node in front of the result removes the special case for the first node.
Hint 3
When one list runs out, attach the rest of the other in one step.
Solution approach
- Create a dummy node and a tail pointer to it. While both lists are non-empty, attach whichever head is smaller to tail.next, advance that list, and advance tail. When one list is exhausted, link tail.next to the remainder of the other, which is already sorted. Return dummy.next. No new nodes are allocated beyond the dummy.
- Dry-run the example, then check boundary cases before explaining time and space costs.
Complexity
O(n + m) time; O(1) auxiliary space.
Report & practice notes
Restated practice version with original examples and explanation. The source is a candidate account, not an official question paper; assessment details can vary. Difficulty is our editorial estimate.
Read the candidate’s source report ↗