Watch 10 video solutions for Merge Two Sorted Lists, a easy level problem involving Linked List, Recursion. This walkthrough by NeetCode has 529,268 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 receive the heads of two sorted singly linked lists. The task is to merge them into one sorted list by reusing the existing nodes. The result must preserve the sorted order while traversing each list only as needed.
Approach 1: Iterative Approach Using a Dummy Node (O(n + m) time, O(1) space)
This approach walks through both lists simultaneously and builds the merged list step by step. A dummy node is created at the start to simplify pointer manipulation. Two pointers compare the current nodes from each list, and the smaller node is appended to the merged list. Then the pointer of the list that contributed the node moves forward. Once one list is exhausted, the remaining nodes from the other list are attached directly since they are already sorted.
The key insight is that you never need to create new nodes or perform extra sorting. You simply relink the existing nodes while iterating through them once. Because each node is visited exactly once, the time complexity is O(n + m), where n and m are the lengths of the two lists. The algorithm uses O(1) additional space since it only maintains a few pointers. This is the most common solution when working with linked list merge operations.
Approach 2: Recursive Approach (O(n + m) time, O(n + m) space)
The recursive strategy relies on the observation that the merged list's head must be the smaller of the two current nodes. Compare list1.val and list2.val. The smaller node becomes the head, and its next pointer is set to the result of merging the remaining part of that list with the other list. This naturally breaks the problem into smaller subproblems until one list becomes empty.
If either list reaches null, the remaining list can be returned directly because it is already sorted. Each recursive call processes one node, leading to a total time complexity of O(n + m). However, recursion uses the call stack, which adds O(n + m) space in the worst case. This pattern is common when solving recursion problems on linked structures because the structure itself mirrors the recursive calls.
Recommended for interviews: Interviewers typically expect the iterative dummy node solution. It demonstrates strong pointer manipulation skills and keeps memory usage at O(1). The recursive version is elegant and concise, but the iterative approach shows better control over linked list operations and avoids stack overhead. Many candidates start by describing the recursive logic conceptually, then implement the iterative version for optimal space usage.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative with Dummy Node | O(n + m) | O(1) | Best general solution; preferred in interviews due to constant extra space |
| Recursive Merge | O(n + m) | O(n + m) | When recursion is acceptable and you want a concise, expressive solution |