Why it works
- The smallest node not taken yet is always at the front of list1 or list2, so comparing the two fronts picks the next node of the answer.
- The dummy stands before the answer, so the first node is appended like all the others. Here it comes from list2, and no extra check was needed for that.
- When one list runs out, the other one is still sorted and larger than everything taken: it goes on whole, in one move.
Complexity
Time O(n + m): every node is taken once. Memory O(1): the answer reuses the nodes, only the dummy is new.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗