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.
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.
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.
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 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 |
Merge Two Sorted Lists - Leetcode 21 - Python • NeetCode • 529,268 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