题目：
Sort a linked list in O(n log n) time using constant space complexity.
题解：
考虑到要求用O(nlogn)的时间复杂度和constant space complexity来sort list，自然而然想到了merge sort方法。同时我们还已经做过了merge k sorted list和merge 2 sorted list。这样这个问题就比较容易了。
不过这道题要找linkedlist中点，那当然就要用最经典的faster和slower方法，faster速度是slower的两倍，当faster到链尾时，slower就是中点，slower的next是下一半的开始点。
解决了这些问题，题目就很容易解出了。
代码如下：
1 public ListNode sortList(ListNode head) {
2 if(head == null|| head.next == null)
3 return head;
4 ListNode slow = head, fast = head, firsthalf = head;
5 while(fast.next!=null&&fast.next.next!=null){
6 slow = slow.next;
7 fast = fast.next.next;
8 }
9 ListNode secondhalf = slow.next;
slow.next = null;
ListNode leftlist = null, rightlist =null;
if(firsthalf!=secondhalf){
leftlist = sortList(firsthalf);
rightlist = sortList(secondhalf);
}
return mergeTwoLists(leftlist, rightlist);
}
public ListNode mergeTwoLists(ListNode leftlist, ListNode rightlist){
if(rightlist == null)
return leftlist;
if(leftlist == null)
return rightlist;
ListNode fakehead = new ListNode(-1);
ListNode ptr = fakehead;
while(rightlist!=null&&leftlist!=null){
if(rightlist.val<leftlist.val){
ptr.next = rightlist;
ptr = ptr.next;
rightlist = rightlist.next;
}else{
ptr.next = leftlist;
ptr = ptr.next;
leftlist = leftlist.next;
}
}
if(rightlist!=null)
ptr.next = rightlist;
if(leftlist!=null)
ptr.next = leftlist;
return fakehead.next;
}