aloalgoSort a Linked List
Hard
You are given the head of a singly linked list.
Your task is to sort the linked list.
Note that:
- The sorting must be performed in-place, meaning you should not create a completely new list.
Return the head of the now-sorted list.
Example 1
Input
4 → 2 → 1 → 3 → null
Output
1 → 2 → 3 → 4 → null
Explanation:
The list is sorted from 4 -> 2 -> 1 -> 3 to 1 -> 2 -> 3 -> 4.
Example 2
Input
-1 → 5 → 3 → 4 → 0 → null
Output
-1 → 0 → 3 → 4 → 5 → null
Explanation:
The list is sorted, including negative numbers.
Example 3
Input
None
Output
None
Explanation:
An empty list remains empty.
Input
4 → 2 → 1 → 3 → null
Output
1 → 2 → 3 → 4 → null