Merge Two Sorted Lists
Updated
Problem statement
Two singly linked lists, list1 and list2, are each sorted in non-decreasing order. Combine all of their nodes into a single list that is also in non-decreasing order, and return the head of that list.
Build the result by relinking the existing nodes, not by creating new ones. Every node of both inputs must appear exactly once, including nodes with equal values. If both inputs are empty, return an empty list.
Function
mergeTwoLists(list1: ListNode, list2: ListNode) → ListNodeExamples
Example 1
list1 = [2,5,9]list2 = [1,5,6,12]return = [1,2,5,5,6,9,12]From list1From list2
- Compare the fronts
2and1: take1fromlist2. Then2fromlist1. - Both fronts are
5. Take either one, then the other, so both copies of5stay in the result. - Next come
6, then9. Nowlist1is used up, so the rest oflist2, which is12, goes at the end.
Example 2
list1 = []list2 = [3,4]return = [3,4]list1 is empty, so the merged list is just list2.
Example 3
list1 = [-3,-3,8]list2 = [-3,10]return = [-3,-3,-3,8,10]From list1From list2
All three nodes with value -3 come first. Then 8 from list1 and 10 from list2 follow in order.
Constraints
- Each list has between
0and50nodes. -100 <= Node.val <= 100- In each list, the values never decrease from head to tail.
More LinkedIn Phone Screen questions
- Maximum Product of a Contiguous SubarrayPHONE SCREEN · Seen Nov 2026
- Maximum Sum of a Contiguous SubarrayPHONE SCREEN · Seen Nov 2026
- Sqrt(x)PHONE SCREEN · Seen Nov 2026
- Total Years of Work ExperiencePHONE SCREEN · Seen Nov 2026
- Sum an Arbitrary-Dimensional ArrayPHONE SCREEN · Seen Oct 2026
- Known Words Matching Phone DigitsPHONE SCREEN · Seen Oct 2026
- Inverse-Depth Nested List SumPHONE SCREEN · Seen Oct 2026
- Valid Number with ExponentsPHONE SCREEN · Seen Oct 2026
- Sort a Quadratic-Transformed ArrayPHONE SCREEN · Seen Oct 2026
- Constant-Time Minimum StackPHONE SCREEN · Seen Oct 2026
Similar questions at other companies
- Reverse a Singly Linked ListBloomberg LP · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions
- Reverse a Singly Linked ListMicrosoft · ONSITE INTERVIEWMicrosoft interview questions
- Merge Two Sorted ListsThe Walt Disney Company · OAThe Walt Disney Company interview questions
- Middle of a Linked ListCisco · PHONE SCREENCisco interview questions
- Reverse a Linked ListApple · PHONE SCREENApple interview questions
- Merge Two Sorted ListsIBM · PHONE SCREENIBM interview questions
- Reverse a Singly Linked ListChubb · PHONE SCREENChubb interview questions
- Detect a Cycle in a Linked ListSalesforce · PHONE SCREENSalesforce interview questions
- Find the Intersection Node of Two Linked ListsVisa · PHONE SCREENVisa interview questions
- Reverse a Linked ListMygate · PHONE SCREENMygate interview questions