Merge Two Sorted Linked Lists
Updated
Problem statement
Two linked lists arrive already in order: walking either one from its head, the values never go down. Values may repeat, and either list may have no nodes at all.
Combine all the nodes of list1 and list2 into a single linked list in the same order, and return the head of that combined list. No node may be dropped or added: if a value appears three times across the two lists, it appears three times in the answer.
Only the sequence of values in the list you return is checked, so you may relink the given nodes or build new ones.
Function
mergeSortedLists(list1: ListNode, list2: ListNode) → ListNodeExamples
Example 1
list1 = [3,8,8,15]list2 = [-1,8,20,21]return = [-1,3,8,8,8,15,20,21]Reading from smallest up: -1 (from list2), 3, the two 8s of list1 and the 8 of list2, then 15, 20 and 21. All eight nodes are kept, so the value 8 appears three times.
Example 2
list1 = [2,2]list2 = [5]return = [2,2,5]Every value in list1 is smaller than 5, so the two 2s come first and the single node of list2 goes at the end.
Example 3
list1 = [-5,0,0]list2 = [-5]return = [-5,-5,0,0]Both lists start with -5, and both of those nodes stay. After them come the two 0s, which are already in order inside list1.
Constraints
- The number of nodes in each list is between
0and1000. -10^5 <= Node.val <= 10^5- Each list is sorted from smallest to largest (equal values may repeat).
More Nutanix Phone Screen questions
- Swap Adjacent Linked List NodesPHONE SCREEN · Seen Mar 2025
- Top K Most Frequent ValuesPHONE SCREEN · Seen Mar 2025
- Unique Triplets Summing to ZeroPHONE SCREEN · Seen Sep 2024
- Find the Duplicate in a Read-Only ArrayPHONE SCREEN · Seen Apr 2021
- Kth Largest Element in an ArrayPHONE SCREEN · Seen Feb 2020
- Kth Smallest Element in a BSTPHONE SCREEN · Seen Feb 2020
- Outline of a Binary TreePHONE SCREEN · Seen Jan 2020
- Print All File and Folder PathsPHONE SCREEN · Seen Dec 2019
- Inorder Predecessor in a BSTPHONE SCREEN · Seen Jan 2019
- K Largest and K Smallest ValuesPHONE SCREEN · Seen Jan 2019
Similar questions at other companies
- Reverse a Linked ListCisco · PHONE SCREENCisco interview questions
- Reverse a Linked ListApple · PHONE SCREENApple interview questions
- Reverse a Singly Linked ListChubb · PHONE SCREENChubb interview questions
- Reverse a Singly Linked ListAdobe · PHONE SCREENAdobe interview questions
- Remove Linked List ElementsBloomberg LP · PHONE SCREENBloomberg LP interview questions
- Reverse a Singly Linked ListExpedia · PHONE SCREEN · ONSITE INTERVIEWExpedia interview questions
- Reverse a Singly Linked ListSuperhuman · PHONE SCREENSuperhuman interview questions
- Merge K Sorted Linked ListsBharatPe · PHONE SCREEN
- Reverse Nodes in K-GroupByteDance · PHONE SCREENByteDance interview questions
- Reverse a Singly Linked ListMicrosoft · ONSITE INTERVIEWMicrosoft interview questions