DSA problem
Merge Two Sorted Lists
You are given the heads of two sorted linked lists list1 and list2. Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists. Return the head of the merged linked list.
Both input lists are sorted in non-decreasing order, which is exactly the precondition that makes the classical two-finger merge from merge sort work in linear time. At every step you only need to compare the two current front nodes and pick the smaller one to append next, without ever needing to look further ahead.
The iterative form of this algorithm uses a dummy head and a moving tail pointer, walking both lists in lockstep. The recursive form expresses the same logic far more succinctly: the merge of two lists is the smaller front node followed by the merge of the remainder, which is a natural fit for recursion.
The optimal recursive approach handles the trivial base cases first — if either list is null, the answer is simply the other list. Otherwise, compare list1.val and list2.val; the smaller node becomes the head of the merged list and its next is set to the recursive merge of the remaining nodes. Each node is visited exactly once, giving O(m + n) time, and the recursion uses O(m + n) call-stack space.
Examples
list1 = [1,2,4], list2 = [1,3,4][1,1,2,3,4,4]list1 = [], list2 = [][]list1 = [], list2 = [0][0]Constraints
- The number of nodes in both lists is in the range [0, 50].
- -100 <= Node.val <= 100
- Both list1 and list2 are sorted in non-decreasing order.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.