Sort a linked list in O(n log n) time using constant space complexity.
The requirement on the time complexity of O(n log n) inspires us to use merge sort on linked list. However, the tricky part of this problem is to only use constant space. The normal top down merge sort does not satisfy this requirement, since it requires additional space.
The solution is to use bootom up merge sort.