Sort a singly linked list in ascending order with better-than-quadratic performance.
Problem
Given the head of a singly linked list, sort the list in ascending order and return the head of the sorted list.
You should aim for an efficient solution that performs well on large lists. Since the list is singly linked, a solution that repeatedly inserts or searches linearly at every step is typically too slow.
Notes
- Reorder the existing nodes; do not create a separate array-based solution unless you are only using it for reasoning.
- The relative order of equal values does not need to be preserved unless your implementation naturally keeps it stable.
Goal
Return the head of the list after sorting all node values in nondecreasing order.
Input Format
- A singly linked list head node
head. - Each node contains an integer value.
Output Format
- Return the head node of the linked list after it has been sorted in ascending order.
Constraints
- The list may be empty.
- The list may contain duplicate values.
- Values may be negative, zero, or positive.
- A solution with time is expected for an interview-quality answer.
Example 1
Input
head = [4,2,1,3]
Output
[1,2,3,4]
Explanation
The nodes are reordered so that the values appear in ascending order.
Example 2
Input
head = [-1,5,3,4,0]
Output
[-1,0,3,4,5]
Explanation
After sorting, the linked list is arranged from smallest to largest value.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.