Sort a linked list in O(n log n) time and constant space

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](sort-a-linked-list)

Solution

Method 1 - Using Mere Sort

We have already seen [Sort a Linked List](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](merge-sort-in-a-linked-list.md/#method-1---recursive)