21. Merge Two Sorted Lists
Merge Two Sorted Lists problem on LeetCode (Easy)
Merge the two sorted linked lists list1 and list2 into one sorted linked list by splicing together the original nodes from the two lists. The key idea in the optimized approach is to use a dummy node and a tail pointer to build the merged list step by step. Compare the current nodes of list1 and list2, attach the smaller one to tail.next, and move that list’s pointer forward. Then move tail forward as well. Once one list runs out, directly attach the remaining part of the other list, since it is already sorted.
Solution:
Use two pointers to traverse both sorted linked lists and merge them directly by re-linking the original nodes.
Time Complexity: O(n + m)
each node from both lists is visited and attached once
Space Complexity: O(1)
only a few pointers are used (dummy, tail, and the input list pointers)
no extra data structure is needed beyond the merged links