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.
1function ListNode(val, next = null) {
2 this.val = val;
3 this.next = next;
4}
The JavaScript solution makes use of a dummy node approach for merging two sorted lists iteratively. The 'tail' variable is employed to maintain a trail of the current end of the merged list. Each iteration of the while loop attaches the node with the lesser value to the 'tail,' thus growing the result list. When finished with both list comparisons, any remainder nodes from whichever initial list still has elements are attached. The dummy node thus provides an efficient entry point for tracking the head of the final, merged linked 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.