【题目描述】
Sort a linked list in O(nlogn) time using constant space complexity.
在O(nlogn) 时间复杂度和常数级的空间复杂度下给链表排序。
【题目链接】
www.lintcode.com/en/problem/sort-list/
【题目解析】
此题可以归并排序。以下归并排序实现的几个要素。
1.按长度等分链表，归并虽然不严格要求等分，但是等分能保证线性对数的时间复杂度。由于链表不能随机访问，故可以先对链表进行遍历求得其长度。
2.合并链表，细节已在Merge Two Sorted Lists | Data Structure and Algorithm中详述。
在按长度等分链表时进行「后序归并」——先求得左半部分链表的表头，再求得右半部分链表的表头，最后进行归并操作。
由于递归等分链表的操作需要传入链表长度信息，故需要另建一辅助函数。
【参考答案】
