Easy
Merge Two Sorted Lists
Weave the two lists together, always taking the smaller head.
Approach
Use a dummy head to simplify edge cases. Repeatedly attach the smaller of the two current nodes and advance that list. When one list runs out, link the remainder of the other. The dummy's next is the merged head.
Time complexity
O(n + m)
Space complexity
O(1)
Common mistake
Not using a dummy node, which forces awkward special-casing of the first element.
See it run, step by step
Generate an interactive lesson for Merge Two Sorted Lists — trace every variable and watch the algorithm execute until it clicks.
Start a lesson on Merge Two Sorted Lists