Merge Two Sorted Lists
Merge Two Sorted Lists is a easy linked list problem solved with the dummy node pattern pattern.
The best approach, optimal (iterative with a dummy node), runs in O(m + n) time and O(1) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from recursive up.
Problem
Merge two sorted linked lists into one sorted list by splicing their nodes together, and return its head.
Examples
Example 1
- Input
list1 = [1, 4, 6], list2 = [2, 4, 9]- Output
[1, 2, 4, 4, 6, 9]
Example 2
- Input
list1 = [], list2 = [0]- Output
[0]
Constraints
- Each list has
0to50nodes, sorted in non-decreasing order.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 9 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Animated walkthrough
A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.
Concepts first, then the problem and every approach, step by step.
Space to play or pause · ← → to jump a step · click or drag the bar to seek
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Recursive | O(m + n) | O(m + n) |
| Optimal (iterative with a dummy node) | O(m + n) | O(1) |
1Recursive
O(m + n)O(m + n)Recursion depth equals the total length.The smaller head goes first; its next is the merge of the rest.
- If either list is empty, return the other.
- If l1.val <= l2.val: l1.next = merge(l1.next, l2); return l1. Else symmetric.
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) return l2;
if (l2 == null) return l1;
if (l1.val <= l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
}
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}class Solution:
def mergeTwoLists(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
if not l1:
return l2
if not l2:
return l1
if l1.val <= l2.val:
l1.next = self.mergeTwoLists(l1.next, l2)
return l1
l2.next = self.mergeTwoLists(l1, l2.next)
return l2class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if (l1 == nullptr) return l2;
if (l2 == nullptr) return l1;
if (l1->val <= l2->val) {
l1->next = mergeTwoLists(l1->next, l2);
return l1;
}
l2->next = mergeTwoLists(l1, l2->next);
return l2;
}
};function mergeTwoLists(l1, l2) {
if (l1 === null) return l2;
if (l2 === null) return l1;
if (l1.val <= l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
}
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}2Optimal (iterative with a dummy node)
O(m + n)O(1)Keep a tail pointer starting at a dummy node. Attach the smaller of the two heads each step, then attach whatever remains.
- tail = dummy.
- While both are non-empty, attach the smaller head and advance it.
- tail.next = the non-empty remainder; return dummy.next.
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(), tail = dummy;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) { tail.next = l1; l1 = l1.next; }
else { tail.next = l2; l2 = l2.next; }
tail = tail.next;
}
tail.next = l1 != null ? l1 : l2;
return dummy.next;
}
}class Solution:
def mergeTwoLists(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode()
tail = dummy
while l1 and l2:
if l1.val <= l2.val:
tail.next = l1
l1 = l1.next
else:
tail.next = l2
l2 = l2.next
tail = tail.next
tail.next = l1 if l1 else l2
return dummy.nextclass Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode* dummy = new ListNode();
ListNode* tail = dummy;
while (l1 != nullptr && l2 != nullptr) {
if (l1->val <= l2->val) { tail->next = l1; l1 = l1->next; }
else { tail->next = l2; l2 = l2->next; }
tail = tail->next;
}
tail->next = l1 != nullptr ? l1 : l2;
return dummy->next;
}
};function mergeTwoLists(l1, l2) {
const dummy = new ListNode();
let tail = dummy;
while (l1 !== null && l2 !== null) {
if (l1.val <= l2.val) { tail.next = l1; l1 = l1.next; }
else { tail.next = l2; l2 = l2.next; }
tail = tail.next;
}
tail.next = l1 !== null ? l1 : l2;
return dummy.next;
}Edge cases to test
- One or both lists empty
- Equal values in both lists
Hints
Hint 1
A dummy head node removes the question of which list supplies the first node.
FAQ
What is the best time complexity for Merge Two Sorted Lists?
Optimal (iterative with a dummy node) runs in O(m + n) time and O(1) extra space.
Which pattern does Merge Two Sorted Lists use?
It is a linked list problem that uses the dummy node pattern pattern. Other problems with the same pattern: Remove Linked List Elements, Delete Nodes From Linked List Present in Array, Rotate List.
Is there a brute force solution for Merge Two Sorted Lists?
Yes. Recursive takes O(m + n) time and O(m + n) space. The smaller head goes first; its next is the merge of the rest.
Which edge cases should I test for Merge Two Sorted Lists?
One or both lists empty; Equal values in both lists.