我要啦免费统计

Sort Linked List Using Contant Space

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.

Read More