Problem Statement
You are given the heads of two sorted linked lists list1 and list2. Merge the two lists into one sorted list.
Approach
Use a dummy node to simplify the head logic. Compare the heads of both lists, attach the smaller node to the current result tail, and advance the pointer. Repeat until one list is empty, then attach the remaining part of the other list.
Time & Space Complexity
Time complexity is O(n + m). Space complexity is O(1) (excluding result list storage).