Merge Two Sorted Lists
Updated
Problem statement
You are given the heads of two singly linked lists, list1 and list2. Each list is sorted in non-decreasing order (each value is less than or equal to the next one).
Merge them into one list that is also sorted in non-decreasing order, and return its head. Keep every node from both lists, including repeated values.
Follow-up: can you build the answer by relinking the existing nodes, using only O(1) extra memory?
Function
mergeTwoLists(list1: ListNode, list2: ListNode) → ListNodeExamples
Example 1
list1 = [1,4,4,9]list2 = [2,4,10]return = [1,2,4,4,4,9,10]From list1From list2
Take the smaller front value each time: 1, then 2, then the three 4s (two from list1, one from list2), then 9 and 10. Every node is kept, including the repeated 4s.
Example 2
list1 = []list2 = [0,3]return = [0,3]list1 is empty, so the answer is just list2.
Example 3
list1 = []list2 = []return = []Both lists are empty, so the merged list is empty too.
Constraints
- The number of nodes in each list is in the range
[0, 2000]. -10^4 <= Node.val <= 10^4- Both
list1andlist2are sorted in non-decreasing order.
More Microsoft Onsite Interview questions
- Longest Substring Without Repeating CharactersONSITE INTERVIEW · Seen Nov 2026
- Valid ParenthesesONSITE INTERVIEW · Seen Nov 2026
- Count a User's Actions in an Event LogONSITE INTERVIEW · Seen Nov 2026
- Smallest Batch Size Within a Step LimitONSITE INTERVIEW · Seen Nov 2026
- Count Subarrays with Equal Even and Odd CountsONSITE INTERVIEW · Seen Nov 2026
- Minimum Time to Rot All OrangesONSITE INTERVIEW · Seen Nov 2026
- Coin ChangeONSITE INTERVIEW · Seen Oct 2026
- Daily USD Totals with Effective-Dated Exchange RatesONSITE INTERVIEW · Seen Oct 2026
- Number Words to Digits in Any LanguageONSITE INTERVIEW · Seen Oct 2026
- Totals from a Tiered Rate TableONSITE INTERVIEW · Seen Oct 2026
Similar questions at other companies
- Detect a Loop in a Linked ListEPAM · ONSITE INTERVIEWEPAM interview questions
- Merge Two Sorted Linked ListsZS · ONSITE INTERVIEWZS interview questions
- Middle Node Of A Linked ListNVIDIA · ONSITE INTERVIEWNVIDIA interview questions
- Build and Check a Palindrome Linked ListOmnissa · ONSITE INTERVIEWOmnissa interview questions
- Reverse a Singly Linked ListGEP · ONSITE INTERVIEW
- Merge Two Sorted Linked ListsApple · ONSITE INTERVIEWApple interview questions
- Reverse Linked ListThe Walt Disney Company · OA · ONSITE INTERVIEWThe Walt Disney Company interview questions
- Detect a Linked-List CycleGoogle · ONSITE INTERVIEWGoogle interview questions
- Detect a Cycle in a Linked ListPeopleStrong · ONSITE INTERVIEWPeopleStrong interview questions
- Reverse a Singly Linked ListBloomberg LP · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions