Sort List

Problem

Sort a linked list in O(n log n) time using constant space complexity.

Example

Given 1->3->2->null, sort it to 1->2->3->null.

Solution

Merge sort. Divide and conquer.

• if there's 0 or 1 node, the list is sorted, return.
• use slow and fast pointer technique to find the mid point.
• recursively call the sort function on the 2 sub lists.
• now the 2 sub lists are sorted, merge them.

The overall time complexity is O(n log n). A related problem is insertion-sort-list, but the complexity of the insertion sort is O(n^2).