Merge Two Sorted Lists
Company: Two Sigma
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
You are given the heads of two singly linked lists, each already sorted in non-decreasing order. Merge them into one sorted linked list and return the head of the merged list.
Requirements:
- Reuse the existing nodes if possible.
- The output must also be sorted in non-decreasing order.
- Handle the case where one or both input lists are empty.
Example:
- List A: `1 -> 2 -> 4`
- List B: `1 -> 3 -> 4`
- Output: `1 -> 1 -> 2 -> 3 -> 4 -> 4`
Quick Answer: This question evaluates proficiency with linked list data structures, pointer manipulation, in-place merging of sorted sequences, and general algorithmic reasoning within the Coding & Algorithms domain.
Merge two sorted linked-list value sequences into one sorted sequence. The list representation makes the task exact-match friendly.
Constraints
- Inputs are sorted in non-decreasing order
Examples
Input: ([1, 2, 4], [1, 3, 4])
Expected Output: [1, 1, 2, 3, 4, 4]
Explanation: Standard merge.
Input: ([], [0])
Expected Output: [0]
Explanation: One empty list.
Input: ([], [])
Expected Output: []
Explanation: Both empty.
Input: ([-3, 1, 1], [-2, 1, 2])
Expected Output: [-3, -2, 1, 1, 1, 2]
Explanation: Duplicates and negatives.
Hints
- Use two pointers and append the smaller current value.