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.