Sort List
Problem Description
Question
Given the head of a linked list, return the list after sorting it in ascending order.
Example 1:
Input:head=[4,2,1,3]
4
2
1
3
null
Output:[1,2,3,4]
1
2
3
4
null
Example 2:
Input:head=[-1,5,3,4,0]
-1
5
3
4
0
null
Output:[-1,0,3,4,5]
-1
0
3
4
5
null
Example 3:
Input:head=[]
null
Output:[]
null
Constraints:
- The number of nodes in the list is in the range [0, 5 * 104].
- -105 <= Node.val <= 105
Follow up: Can you sort the linked list in O(n logn) time and O(1) memory (i.e. constant space)?
Solve it on LeetCode
Approaches
1. Merge Sort (Top-Down)
Intuition:
Merge Sort is an efficient and systematic way of sorting linked lists because it divides the list into halves, sorts, and then merges them back. In a linked list, accessing middle elements directly isn't as straightforward as arrays. However, we can find the middle using the "fast and slow pointer" strategy.
- Divide: Use the fast-slow pointer method to divide the list into two halves.
- Conquer: Recursively sort the sublists.
- Combine: Merge the two sorted halves.
Code:
Complexity Analysis
- Time Complexity: O(n log n), where n is the number of nodes in the linked list. Each split divides the list into two halves, and merging takes linear time.
- Space Complexity: O(log n) due to the recursive stack space.
2. Merge Sort (Bottom-Up)
Intuition:
The bottom-up merge sort iteratively merges sublists of increasing size. This approach doesn't use recursion, thus avoids the overhead of recursive function calls — potentially saving stack space and making it iterative.
- Iteratively combine sublists of size 1, 2, 4, and so forth.
- Start from small chunks, keep combining until the entire list is sorted.
Code:
Complexity Analysis
- Time Complexity: O(n log n), similar to the top-down approach. Each pass through the list doubling the size effectively achieves the merge.
- Space Complexity: O(1), this is an in-place sorting algorithm with no additional space use aside from a few pointers.