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

Sort a Linked List

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