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.The key idea behind Merge Two Sorted Lists is similar to the merge step in the merge sort algorithm. Since both linked lists are already sorted, you can repeatedly compare the current nodes of each list and attach the smaller value to the result list. This guarantees that the final merged list remains sorted.
A common technique is to use a dummy node to simplify pointer manipulation. Maintain a pointer that always points to the end of the merged list, then move through both lists while comparing values. Whichever node has the smaller value is appended next, and its pointer moves forward.
Another elegant approach uses recursion. At each step, compare the heads of the two lists and recursively merge the remaining nodes. The smaller node becomes the head of the merged result.
Both approaches process each node exactly once, giving a time complexity of O(n + m), where n and m are the lengths of the two lists.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Iterative Merge (Dummy Node) | O(n + m) | O(1) |
| Recursive Merge | O(n + m) | O(n + m) recursion stack |
NeetCode
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.
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.
1#include <stdio.h>
2#include <stdlib.h>
3
4struct ListNode {
5 int val;
6 struct ListNode
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.
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.
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.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, this is a common foundational linked list problem frequently asked in technical interviews, including FAANG-style interviews. It tests understanding of pointers, recursion, and basic algorithmic thinking.
Yes, the problem has a clean recursive solution. At each step you compare the heads of both lists and recursively merge the remaining nodes. The smaller node becomes the next node in the merged list.
The optimal approach is to iterate through both sorted linked lists and merge them by always selecting the smaller current node. Using a dummy head node simplifies pointer management. This method runs in O(n + m) time and uses O(1) extra space.
A solid understanding of singly linked lists and pointer manipulation is essential. You should know how to traverse lists, update next pointers, and handle edge cases like empty 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.