Problem
Given a linked list, sort it in O(n log n) time and constant space.
Examples
Example 1:
Input: head = [4,2,1,3]
Output: [1,2,3,4]
Similar Problem
Solution
Method 1 - Using Mere Sort
We have already seen Sort a Linked List, but here we have to sort in O(n log n)
time and O(1)
space. So, we can use merge sort to meet the constraints. Merge Sort in a Linked list#Method 1 - Recursive