You’re interviewing for a backend or data engineering role at a FAANG-level company. The interviewer describes a real product scenario:
A large-scale backend system processes ordered streams of data coming from multiple services. Each service produces a sorted stream of records, such as timestamps, scores, or IDs.
Before further processing, the system needs to merge two already sorted streams into a single sorted sequence while preserving order and minimizing memory usage.
Each stream is represented as a singly linked list, and the system requires an efficient merge without creating unnecessary new nodes.
This is a common practice coding problem for DSA question might ask in Google, Amazon, Netflix, Meta, Apple, Microsoft, Uber, and Bloomberg interviews.
Your Task
Given the heads of two sorted singly linked lists list1 and list2, merge them into one sorted linked list and return the head of the merged list.
The new list should be made by splicing together the nodes of the first two lists.
Input Format
list1: head of the first sorted linked listlist2: head of the second sorted linked list
Each node is defined as:
ListNode { int val; ListNode next; }
Output Format
- Return the head of the merged sorted linked list
Examples
Example 1:
Input: list1 = [1,2,4]
list2 = [1,3,4]
Output: [1,1,2,3,4,4]
Example 2:
Input: list1 = []
list2 = []
Output: []
Example 3:
Input: list1 = []
list2 = [0]
Output: [0]