Merge Linked Lists
Filed under Deloitte · Also reported at Dell
Free read 3 of 3Confirm whether inputs can be modified in-place and how to handle empty lists.
The question
Merge two sorted linked lists and return it as a sorted list. The list should be made by splicing together the nodes of the first two lists.
Constraints
- The number of nodes in both lists is in the range [0, 50].
- -100 <= Node.val <= 100
- Both l1 and l2 are sorted in non-decreasing order.
Examples
- Input
- l1 = [1,2,4], l2 = [1,3,4]
- Output
- [1,1,2,3,4,4]
- Why
- Splices the nodes together to maintain non-decreasing order.
Approach
Confirm whether inputs can be modified in-place and how to handle empty lists.
Collect all values into an array, sort the array, and construct a new linked list. Time complexity O(N log N).
Use a dummy head node and a pointer to iteratively pick the smaller node between l1 and l2, attaching it to the merged list. Time complexity O(N + M).
One or both lists are initially empty.
Solution
O(N + M) time, O(1) space
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def mergeTwoLists(l1: ListNode, l2: ListNode) -> ListNode:
dummy = cur = ListNode(0)
while l1 and l2:
if l1.val < l2.val:
cur.next, l1 = l1, l1.next
else:
cur.next, l2 = l2, l2.next
cur = cur.next
cur.next = l1 or l2
return dummy.next
Tips
- What they are testing: Test with empty lists, lists of different lengths, and lists with duplicate values.
- Common mistake: Forgetting to advance the pointer on the resulting list or failing to attach the remaining nodes when one list is exhausted.
Related Deloitte questions
Collected from public candidate posts and coding forums. Updated Nov 2026.