Merge Two Sorted Lists
Merge two sorted linked lists into one sorted list by splicing their nodes together, and return its head.
A way to picture it
Two single-file queues of people, each sorted by height, need to merge through one doorway. The doorman looks at the two people at the front and waves the shorter one through. When one queue runs out, the rest of the other just walks straight in.
How to approach it
Use a dummy head and a tail pointer. Repeatedly attach the smaller front node, then attach whatever remains.
Example
Input: {"list1":[1,2,4],"list2":[1,3,4]}. Output: [1,1,2,3,4,4].
Complexity: O(n + m) time and O(1) space. Each node is attached once; nodes are reused, not copied.
This page includes an animated walkthrough, Java and Python solutions, and a question to check your understanding.