Merge Two Sorted Lists - Solution & Explanation
Problem Statement
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:
- The number of nodes in both lists is in the range
[0, 50]. -100 <= Node.val <= 100- Both
list1andlist2are sorted in non-decreasing order.
Approach Overview
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 1: Iterative Approach Using a Dummy Node
This approach involves using a dummy node to ease the merging process. A dummy node is a temporary node that helps in easily managing edge cases such as initializing the result list and returning the correct head of the list. We will iterate over both lists, and in each iteration, we'll add the smallest current node to our result list. The time complexity of this method is O(n + m), where n and m are the lengths of the two lists.
This C program implements the iterative approach using a dummy node. We create a dummy node that acts as a starting point for our merged list. A pointer 'tail' is used to keep track of the end of the merged list. We iterate through the lists, always choosing the smaller head node and updating our tail pointer. If one list is exhausted before the other, we simply attach the remainder of the other list to the merged list. Finally, the next node of our dummy node is the head of our merged list.
Complexity
Time Complexity: O(n + m), where n and m are the lengths of list1 and list2.
Space Complexity: O(1), since we are only using a constant amount of extra space.
Approach 2: Recursive Approach
The recursive approach simplifies merging by using recursive function calls to naturally handle merging nodes. This method leverages the call stack to handle the comparisons and merging order, with each function call processing pairwise comparisons when identifying the next node for the merged list. The recursion terminates when either list is fully traversed, thereby appending the remainder of the other list if needed. The recursive nature implicitly manages the combination of currently smallest nodes. The complexity is linear relative to the combined size of the lists.
This recursive C solution merges two lists by repeatedly choosing the node with the smaller value. The function returns nodes by linking them through recursive calls that serve as connections for adjoining nodes. Upon encountering null for either input list, the method returns the other list to connect any remaining nodes. In each call, the smaller node is chosen and its 'next' linkage field is updated to sequence-based recursive evaluations of the list tails until fully sorted into the merged output.
Complexity
Time Complexity: O(n + m), where n and m are the lengths of list1 and list2.
Space Complexity: O(n + m), due to recursive stack space required by function calls.
Approach 3: Recursion
First, we judge whether the linked lists l_1 and l_2 are empty. If one of them is empty, we return the other linked list. Otherwise, we compare the head nodes of l_1 and l_2:
- If the value of the head node of
l_1is less than or equal to the value of the head node ofl_2, we recursively call the functionmergeTwoLists(l_1.next, l_2), and connect the head node ofl_1with the returned linked list head node, and return the head node ofl_1. - Otherwise, we recursively call the function
mergeTwoLists(l_1, l_2.next), and connect the head node ofl_2with the returned linked list head node, and return the head node ofl_2.
The time complexity is O(m + n), and the space complexity is O(m + n). Here, m and n are the lengths of the two linked lists respectively.
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C#
Ruby
PHP
Approach 4: Iteration
We can also use iteration to implement the merging of two sorted linked lists.
First, we define a dummy head node dummy, then loop through the two linked lists, compare the head nodes of the two linked lists, add the smaller node to the end of dummy, until one of the linked lists is empty, then add the remaining part of the other linked list to the end of dummy.
Finally, return dummy.next.
The time complexity is O(m + n), where m and n are the lengths of the two linked lists respectively. Ignoring the space consumption of the answer linked list, the space complexity is O(1).
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C#
Ruby
PHP
Complexity Comparison
| Approach | Complexity |
|---|---|
| Iterative Approach Using a Dummy Node | Time Complexity: O(n + m), where n and m are the lengths of list1 and list2. |
| Recursive Approach | Time Complexity: O(n + m), where n and m are the lengths of list1 and list2. |
| Recursion | — |
| Iteration | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Merge Two Sorted Lists - Leetcode 21 - Python • NeetCode • 550,270 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Merge Two Sorted Lists easy or hard?
Merge Two Sorted Lists Python/Java solution
How to solve Merge Two Sorted Lists in O(n)?
What is the best approach for Merge Two Sorted Lists?
Is Merge Two Sorted Lists asked at Google/Amazon/Meta?
What data structure is used in Merge Two Sorted Lists?
What is the time complexity of Merge Two Sorted Lists?
Ready to solve this problem?
Practice Merge Two Sorted Lists with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor