Given two sorted linked lists, merge them into one sorted list. Reuse the existing nodes.
DSA Animator › DSA Revision › Linked List › Merge Two Sorted Lists
Remember: a dummy head makes building a list easy. Always take the smaller head. The video solves Merge Two Sorted Lists (LeetCode 21, Easy) with the Two Pointers Merge pattern from the Linked List topic, and you can replay every step in the interactive Merge Two Sorted Lists animation.
Given two sorted linked lists, merge them into one sorted list. Reuse the existing nodes.
For 1, 2, 4 and 1, 3, 4, the result is 1, 1, 2, 3, 4, 4.
Collecting all values, sorting them and building a new list costs O of n log n. Both lists are already sorted, so just merge.
Start with a dummy node and a tail pointer. Compare the two heads, attach the smaller one to the tail, and advance that list. When one list runs out, attach the rest of the other.
1 versus 1, take the first one. Then 2 versus 1, take 1 from the second list. 2 versus 3, take 2, then 4 versus 3, take 3. 4 versus 4, take the first 4, and the second list has one 4 left. Attach it, giving 1, 1, 2, 3, 4, 4.
In code, create a dummy and a tail. While both lists have nodes, link the smaller head to the tail and move forward. Then attach whichever list remains. Return dummy dot next, so it's O of m plus n time and O of 1 space.
Remember: a dummy head makes building a list easy. Always take the smaller head.