Merge two sorted linked lists
Company: Two Sigma
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
Given two singly linked lists sorted in ascending order, merge them into one singly linked list that is also sorted in ascending order.
Requirements:
- Each input list may be empty.
- Node values are integers.
- Reuse the existing nodes if possible.
- Return the head of the merged list.
- Target time complexity: O(n + m), where n and m are the lengths of the two lists.
Quick Answer: This question evaluates proficiency with linked list data structures, pointer manipulation, in-place merging concepts, and algorithmic efficiency within the Coding & Algorithms domain.