EasyLinked ListsFree practice
Merge Two Sorted Lists
Asked atamazongooglemicrosoftapplebloomberg
01 · Problem
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.
02 · Examples
Example 01
Input
list1 = [1,2,4], list2 = [1,3,4]
Output
[1,1,2,3,4,4]
Compare nodes from both lists. 1<=1, take list1's 1. Then 1<=2 so take list2's 1. Then 2<=3 so take list1's 2. Then 3<=4, take list2's 3. Then 4=4, take list1's 4. Finally take list2's 4.
Example 02
Input
list1 = [], list2 = [0]
Output
[0]
list1 is empty, so the result is simply list2.
03 · Constraints
- 01The number of nodes in both lists is in the range [0, 50].
- 02-100 <= Node.val <= 100
- 03Both list1 and list2 are sorted in non-decreasing order.
04 · Optimal complexity
- Time
- O(n + m)
- Space
- O(1)
05 · Two ways to work on it
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.