Merge Two Sorted Lists
EasyPrompt
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.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach involves collecting all the values from both linked lists into an auxiliary data structure like an array, sorting this array, and then constructing a new sorted linked list from the sorted values.
Algorithm
-
- Create a list (e.g.,
ArrayList) to store node values.
- Create a list (e.g.,
-
- Traverse
list1from head to tail, adding each node's value to the list.
- Traverse
-
- Traverse
list2from head to tail, adding each node's value to the list.
- Traverse
-
- Sort the list of values using a standard sorting algorithm.
-
- Create a new dummy head
ListNodeto serve as the starting point for the result list.
- Create a new dummy head
-
- Iterate through the sorted values, create a new
ListNodefor each value, and append it to the result list.
- Iterate through the sorted values, create a new
-
- Return the
nextnode of the dummy head.
- Return the
Walkthrough
The core idea is to transform the linked list problem into an array problem, which is often easier to handle. First, we iterate through both list1 and list2, adding each node's value to a list. After collecting all values, we use a standard sorting algorithm (like the one provided by Collections.sort() in Java) to sort the list of values in non-decreasing order. Finally, we create a new linked list. We start with a dummy head node to simplify insertion. Then, we iterate through the sorted list of values, creating a new ListNode for each value and appending it to our new linked list. The head of this newly created list is then returned.
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */class Solution { public ListNode mergeTwoLists(ListNode list1, ListNode list2) { if (list1 == null) return list2; if (list2 == null) return list1; java.util.List<Integer> values = new java.util.ArrayList<>(); ListNode current = list1; while (current != null) { values.add(current.val); current = current.next; } current = list2; while (current != null) { values.add(current.val); current = current.next; } java.util.Collections.sort(values); ListNode dummyHead = new ListNode(0); ListNode tail = dummyHead; for (int val : values) { tail.next = new ListNode(val); tail = tail.next; } return dummyHead.next; }}Complexity
Time
O((m+n) log(m+n))
Space
O(m + n)
Trade-offs
Pros
Simple to conceptualize and implement.
Leverages well-known and optimized built-in sorting algorithms.
Cons
Highly inefficient as it does not utilize the pre-sorted nature of the input lists.
Requires extra space proportional to the total number of nodes, which is suboptimal.
Creates an entirely new list of nodes instead of reusing the existing ones.
This approach solves the problem recursively. The main idea is that the head of the merged list is the node with the smaller value from the heads of the two input lists. The rest of the merged list is formed by recursively merging the remaining parts of the lists.
Algorithm
-
- Define the base cases: If
list1is null, returnlist2. Iflist2is null, returnlist1.
- Define the base cases: If
-
- Compare the values at the heads of
list1andlist2.
- Compare the values at the heads of
-
- If
list1.val <= list2.val, the result's head islist1. Recursively call the function withlist1.nextandlist2and assign the result tolist1.next.
- If
-
- Return
list1.
- Return
-
- Otherwise (if
list2.val < list1.val), the result's head islist2. Recursively call the function withlist1andlist2.nextand assign the result tolist2.next.
- Otherwise (if
-
- Return
list2.
- Return
Walkthrough
The recursion is defined by a function that takes two nodes, l1 and l2, as input and returns the head of the merged list.
Base Cases:
- If
l1is null, it means we have exhausted the first list, so the merged list is simply the rest ofl2. We returnl2. - Similarly, if
l2is null, we returnl1.
Recursive Step:
- We compare the values of the current heads,
l1.valandl2.val. - If
l1.valis smaller or equal, thenl1is the head of the merged list. Thenextpointer ofl1should point to the result of merging the rest ofl1(l1.next) withl2. We make a recursive call:l1.next = mergeTwoLists(l1.next, l2). Then we returnl1. - Otherwise,
l2is the head. We setl2.nextto the result of mergingl1with the rest ofl2(l2.next) vial2.next = mergeTwoLists(l1, l2.next). Then we returnl2.
This process continues until one of the lists becomes null, at which point the base cases handle the termination.
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */class Solution { public ListNode mergeTwoLists(ListNode list1, ListNode list2) { // Base case: if one list is null, return the other. if (list1 == null) { return list2; } if (list2 == null) { return list1; } // Recursive step: compare heads and recurse. if (list1.val <= list2.val) { list1.next = mergeTwoLists(list1.next, list2); return list1; } else { list2.next = mergeTwoLists(list1, list2.next); return list2; } }}Complexity
Time
O(m + n)
Space
O(m + n)
Trade-offs
Pros
The code is often more concise and elegant than the iterative version.
Follows a natural divide-and-conquer pattern which can be easier to reason about.
Cons
Can lead to a stack overflow error for very long lists due to deep recursion (though not an issue with the problem's constraints).
The space complexity of O(m+n) due to the recursion stack is not optimal compared to the iterative solution.
This is the most optimal approach. It involves iterating through both lists simultaneously and building the merged list by picking the smaller node at each step. A dummy head node is used to simplify the code, avoiding special handling for the first node of the merged list.
Algorithm
-
- Create a
dummynode to act as a sentinel head for the result list.
- Create a
-
- Create a
currentpointer, initialized todummy.
- Create a
-
- Loop while both
list1andlist2are not null.
- Loop while both
-
- Inside the loop, compare
list1.valandlist2.val.
- Inside the loop, compare
-
- If
list1.val <= list2.val, setcurrent.next = list1and advancelist1.
- If
-
- Else, set
current.next = list2and advancelist2.
- Else, set
-
- In both cases, advance
currenttocurrent.next.
- In both cases, advance
-
- After the loop, one list may have remaining nodes. Append the non-null list to
current.next.
- After the loop, one list may have remaining nodes. Append the non-null list to
-
- Return
dummy.next.
- Return
Walkthrough
We start by creating a dummy node, which will act as a placeholder for the head of the merged list. We also create a current pointer, initialized to this dummy node. This current pointer will always point to the last node in the merged list we've built so far.
We then iterate as long as both list1 and list2 have nodes. In each iteration:
- We compare
list1.valandlist2.val. - If
list1.valis smaller or equal, we linkcurrent.nexttolist1and advancelist1to its next node. - Otherwise, we link
current.nexttolist2and advancelist2to its next node. - In either case, we move
currentforward to the node we just added (current = current.next).
After the loop terminates, one of the lists might still have remaining nodes (since the other one became null). These remaining nodes are already sorted, so we can simply append the non-null list to the end of our merged list.
Finally, the merged list starts at dummy.next. We return this node.
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */class Solution { public ListNode mergeTwoLists(ListNode list1, ListNode list2) { // Create a dummy node to serve as the start of the merged list. ListNode dummy = new ListNode(-1); // Create a pointer to the last node of the merged list. ListNode current = dummy; // Traverse both lists until one of them is exhausted. while (list1 != null && list2 != null) { if (list1.val <= list2.val) { current.next = list1; list1 = list1.next; } else { current.next = list2; list2 = list2.next; } current = current.next; } // Append the remaining nodes from the non-empty list. if (list1 != null) { current.next = list1; } else { current.next = list2; } // The merged list is the next of the dummy node. return dummy.next; }}Complexity
Time
O(m + n)
Space
O(1)
Trade-offs
Pros
Optimal time complexity of O(m+n).
Optimal space complexity of O(1) (constant space).
Avoids recursion, preventing any potential for stack overflow issues on extremely large inputs.
Cons
The code might be slightly more verbose than the recursive version due to manual pointer management.
Solutions
Solution
/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} list1 * @param {ListNode} list2 * @return {ListNode} */ var mergeTwoLists = function (list1, list2) { const dummy = new ListNode(); let curr = dummy; while (list1 && list2) { if (list1.val <= list2.val) { curr.next = list1; list1 = list1.next; } else { curr.next = list2; list2 = list2.next; } curr = curr.next; } curr.next = list1 || list2; return dummy.next; };/** * Definition for singly-linked list. * public class ListNode { * public int val; * public ListNode next; * public ListNode(int val=0, ListNode next=null) { * this.val = val; * this.next = next; * } * } */ public class Solution { public ListNode MergeTwoLists ( ListNode list1 , ListNode list2 ) { ListNode dummy = new ListNode (); ListNode cur = dummy ; while ( list1 != null && list2 != null ) { if ( list1 . val <= list2 . val ) { cur . next = list1 ; list1 = list1 . next ; } else { cur . next = list2 ; list2 = list2 . next ; } cur = cur . next ; } cur . next = list1 == null ? list2 : list1 ; return dummy . next ; } }/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode mergeTwoLists ( ListNode list1 , ListNode list2 ) { ListNode dummy = new ListNode (); ListNode curr = dummy ; while ( list1 != null && list2 != null ) { if ( list1 . val <= list2 . val ) { curr . next = list1 ; list1 = list1 . next ; } else { curr . next = list2 ; list2 = list2 . next ; } curr = curr . next ; } curr . next = list1 == null ? list2 : list1 ; return dummy . next ; } }/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode * mergeTwoLists ( ListNode * list1 , ListNode * list2 ) { ListNode * dummy = new ListNode (); ListNode * curr = dummy ; while ( list1 && list2 ) { if ( list1 -> val <= list2 -> val ) { curr -> next = list1 ; list1 = list1 -> next ; } else { curr -> next = list2 ; list2 = list2 -> next ; } curr = curr -> next ; } curr -> next = list1 ? list1 : list2 ; return dummy -> next ; } };# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next # without ops after while loop class Solution : def mergeTwoLists ( self , list1 : Optional [ ListNode ], list2 : Optional [ ListNode ]) -> Optional [ ListNode ]: dummy = ListNode () current = dummy while list1 or list2 : v1 = list1 . val if list1 else float ( 'inf' ) v2 = list2 . val if list2 else float ( 'inf' ) if v1 < v2 : current . next = list1 list1 = list1 . next else : current . next = list2 list2 = list2 . next current = current . next return dummy . next ############ # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution : def mergeTwoLists ( self , list1 : Optional [ ListNode ], list2 : Optional [ ListNode ] ) -> Optional [ ListNode ]: dummy = ListNode () curr = dummy while list1 and list2 : if list1 . val <= list2 . val : curr . next = list1 list1 = list1 . next else : curr . next = list2 list2 = list2 . next curr = curr . next curr . next = list1 or list2 return dummy . next """ curr.next = list1 or list2 better than: if list1: current.next = list1 if list2: current.next = list2 """ ############ # recursion class ListNode : def __init__ ( self , val = 0 , next = None ): self . val = val self . next = next class Solution : def mergeTwoLists ( self , l1 : ListNode , l2 : ListNode ) -> ListNode : if not l1 : # If l1 is empty, return l2 return l2 if not l2 : # If l2 is empty, return l1 return l1 if l1 . val < l2 . val : l1 . next = self . mergeTwoLists ( l1 . next , l2 ) return l1 else : l2 . next = self . mergeTwoLists ( l1 , l2 . next ) return l2Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.