Watch 10 video solutions for Merge Two Sorted Lists, a easy level problem involving Linked List, Recursion. This walkthrough by NeetCode has 438,617 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
Example 1:
Input: list1 = [1,2,4], list2 = [1,3,4] Output: [1,1,2,3,4,4]
Example 2:
Input: list1 = [], list2 = [] Output: []
Example 3:
Input: list1 = [], list2 = [0] Output: [0]
Constraints:
[0, 50].-100 <= Node.val <= 100list1 and list2 are sorted in non-decreasing order.Problem Overview: You are given two sorted singly linked lists. The task is to merge them into a single sorted list by rearranging existing nodes. The merged list must maintain ascending order without creating new nodes unnecessarily.
Approach 1: Iterative Merge Using a Dummy Node (O(n+m) time, O(1) space)
This method simulates the merge step of merge sort. Create a dummy node that acts as the starting anchor for the merged list. Maintain a pointer tail that always points to the last node in the merged result. Compare the current nodes of both lists, attach the smaller node to tail, and advance that list's pointer. Continue until one list is exhausted, then append the remaining nodes from the other list.
The key insight is that both lists are already sorted. You only need a single pass with pointer comparisons. The dummy node simplifies edge cases such as initializing the head of the result list. Since nodes are reused instead of copied, the algorithm runs in O(n+m) time with O(1) extra space. This is the most common technique used when working with linked list merging problems.
Approach 2: Recursive Merge (O(n+m) time, O(n+m) space)
The recursive strategy mirrors the same comparison logic but expresses it naturally through function calls. Compare the heads of the two lists. The smaller node becomes the head of the merged result, and its next pointer is set to the result of merging the remainder of the lists recursively. If one list becomes empty, return the other list directly.
This approach is elegant and concise because each recursive call solves a smaller version of the same problem. However, every call adds a stack frame, which results in O(n+m) auxiliary space due to recursion depth. For large lists this can risk stack overflow in some languages. The approach is still useful when practicing recursion or demonstrating problem decomposition.
Recommended for interviews: The iterative dummy node approach is what most interviewers expect. It shows you understand pointer manipulation, efficient in-place merging, and edge case handling in linked list problems. Mentioning the recursive version demonstrates deeper understanding, but the iterative version is preferred because it achieves O(1) auxiliary space and avoids recursion overhead.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Merge Using Dummy Node | O(n+m) | O(1) | Best general solution for interviews; efficient pointer manipulation without recursion. |
| Recursive Merge | O(n+m) | O(n+m) | Useful when practicing recursion or when code simplicity is preferred over stack efficiency. |