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值大的节点拆分到两个链表中。然后对这两个链表分别进行快速排序，然后把这三部分组装起来就好了。代码如下：
1 public class Solution { 2 public ListNode sortList(ListNode head) { 3 if(head==null || head.next==null) return head; 4 5 ListNode lefthead = null; 6 ListNode righthead = null; 7 ListNode mid = head; 8 head = head.next; 9 mid.next = null; 10 ListNode midtail = mid; 11 12 while(head!=null){ //把链表拆分成三部分 13 ListNode temp = head; 14 head = head.next; 15 if(temp.val < mid.val){ //比head.val小的部分 16 temp.next = lefthead; 17 lefthead = temp; 18 } 19 else if(temp.val == mid.val){ 20 temp.next = mid; 21 mid = temp; 22 } 23 else{ 24 temp.next = righthead; //比head.val大的部分 25 righthead = temp; 26 } 27 } 28 29 righthead = sortList(righthead);//把三部分组装起来 30 if(lefthead==null){ 31 midtail.next = righthead; 32 return mid; 33 } 34 lefthead = sortList(lefthead); 35 36 ListNode tmp = lefthead; 37 while(tmp.next!=null) tmp = tmp.next; 38 tmp.next = mid; 39 midtail.next = righthead; 40 return lefthead; 41 } 42 }