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 data processing system ingests events, logs, or records that are stored temporarily as a singly linked list. Due to streaming ingestion or distributed writes, the data arrives out of order.
Before performing analytics, indexing, or downstream processing, the system must sort the linked list by value. Because the data is stored as a linked list, random access is not available, and converting the list to an array is discouraged due to memory constraints.
The platform expects an efficient in-place sorting solution with optimal time complexity.
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 head of a singly linked list, sort the list in ascending order and return the head of the sorted list.
You must achieve O(n log n) time complexity.
Input Format
head: the head node of a singly linked list
Each node is defined as:
ListNode { int val; ListNode next; }
Output Format
- Return the head of the sorted linked list