21. Merge Two Sorted Lists
Merge Two Sorted Lists (LeetCode 21) is a Easy Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Linked List Manipulation Patterns pattern, in the Merging Two Sorted Lists subpattern.
- Blind 75 · #20 of 75 · Linked List
- NeetCode 150 · #36 of 150 · Linked List
- NeetCode 250 · #75 of 250 · Linked List
How to solve Merge Two Sorted Lists
Merge Two Sorted Lists is a Merge Two Sorted Linked Lists problem, part of Linked List Manipulation Patterns. Learn to merge two sorted linked lists efficiently. Foundation for merge sort and k-way merge problems.
Work towards the solution in these steps:
- Think about how you can traverse both linked lists simultaneously to compare their elements.
- Consider using a dummy node to simplify the process of merging the two lists.
- At each step, attach the smaller current node from either list to the merged list and advance that list's pointer.
The reference solution runs in O(n + m) time and O(n + m) space.
The Merge Two Sorted Lists solution and editorial walks through the full approach with reference code.
Problem statement
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 list1 and list2 are sorted in non-decreasing order.
Topics and companies
Topics: Linked List, Recursion.
Reported in interviews at Amazon, Adobe, Bloomberg, Capital One, Facebook, Microsoft, Oracle, LinkedIn, Uber, VMware, IBM, ByteDance.
How to practise Merge Two Sorted Lists on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n + m) time and O(n + m) space.
Open Merge Two Sorted Lists in the code editor, or read the Merge Two Sorted Lists editorial for a worked solution with its approach and complexity analysis.
Where Merge Two Sorted Lists sits in the DSA pattern sheet
- Linked List Manipulation Patterns pattern guide
- Merging Two Sorted Lists subpattern
- The full DSA patterns sheet
Problems related to Merge Two Sorted Lists
Other problems that use the same Merging Two Sorted Lists and Linked List Manipulation Patterns techniques:
- Add Two Numbers — Medium, same pattern
- Insert Greatest Common Divisors in Linked List — Medium, same pattern
- Intersection of Two Linked Lists — Easy, same pattern
- Minimum Index Sum of Two Lists — Easy, same pattern
- Odd Even Linked List — Medium, same pattern
- Palindrome Linked List — Easy, same pattern
Merge Two Sorted Lists FAQ
What is the LeetCode number of Merge Two Sorted Lists?
Merge Two Sorted Lists is LeetCode problem 21, rated Easy.
What pattern is used to solve Merge Two Sorted Lists?
Merge Two Sorted Lists is a Merge Two Sorted Linked Lists problem. It belongs to the Linked List Manipulation Patterns pattern, in the Merging Two Sorted Lists subpattern.
What is the time complexity of Merge Two Sorted Lists?
The reference solution runs in O(n + m) time and O(n + m) space.
Which companies ask Merge Two Sorted Lists?
Merge Two Sorted Lists has been reported in interviews at Amazon, Adobe, Bloomberg, Capital One, Facebook, Microsoft, Oracle, LinkedIn, Uber, VMware, IBM, ByteDance.