Sort a linked list in O(n log n) time using constant space complexity.
排序问题是我们遇到的一个老问题，从大一开始我们就学习了各种排序算法，大部分是基于数组的，比如冒泡排序，插入排序，快速排序等。这其中冒泡排序，插入排序的算法复杂度都是O(n2)，插入排序的时间复杂度为O(nlogn)。对于这个题目，显然我们不能使用冒泡排序和插入排序，因为这样时间复杂度不满足要求，那么链表适合用快速排序吗？答案是肯定的，链表的结构还是非常方便使用快速排序的。
快速排序的特点是：如果待排序的数字列表越散乱，效果越好。如果数字列表是完全升序或者完全降序，快排的效果最差。最好情况下时间复杂度为O(nlogn)，最坏情况为O(n2)。
快速排序的思想是：1.选一个key值；2.把小于key值的数移到key的左边；3.把大于key值的数移到key的右边；4.对左半部分和右半部分使用快速排序算法。
在对链表进行快速排序时，我们可以选择头结点作为key值，然后遍历链表，把比头结点val值小的节点和比头结点val值大的节点拆分到两个链表中。然后对这两个链表分别进行快速排序，然后把这三部分组装起来就好了。代码如下：
public class Solution {
public ListNode sortList(ListNode head) {
if(head==null || head.next==null) return head;
ListNode lefthead = null;
ListNode righthead = null;
ListNode mid = head;
head = head.next;
mid.next = null;
ListNode midtail = mid;
while(head!=null){ //把链表拆分成三部分
ListNode temp = head;
head = head.next;
if(temp.val < mid.val){ //比head.val小的部分
temp.next = lefthead;
lefthead = temp;
}
else if(temp.val == mid.val){
temp.next = mid;
mid = temp;
}
else{
temp.next = righthead; //比head.val大的部分
righthead = temp;
}
}
righthead = sortList(righthead);//把三部分组装起来
if(lefthead==null){
midtail.next = righthead;
return mid;
}
lefthead = sortList(lefthead);
ListNode tmp = lefthead;
while(tmp.next!=null) tmp = tmp.next;
tmp.next = mid;
midtail.next = righthead;
return lefthead;
}
}