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.
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.
C++
Java
Python
C#
JavaScript
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.
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.
C++
Java
Python
C#
JavaScript
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 | 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. |
| 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. |
Merge Two Sorted Lists - Leetcode 21 - Python • NeetCode • 438,617 views views
Watch 9 more video solutions →Practice Merge Two Sorted Lists with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor