[lintcode]98. 链表排序

链接：http://www.lintcode.com/zh-cn/problem/sort-list/

在 O(n log n) 时间复杂度和常数级的空间复杂度下给链表排序。

您在真实的面试中是否遇到过这个题？ 

Yes

样例

给出 1->3->2->null，给它排序变成 1->2->3->null.

思路：对链表进行排序，时间复杂度为O(n log n)，最好使用归并排序，快速排序在最坏的情况下时间复杂度为O(n^2)。利用归并的方法进行排序，完成两个主要功能即可：拆分和合并。拆分用到了比较好的方法就是利用快慢指针进行，每次找到链表的中间部分进行拆解。合并可以利用两种方式：一种是非递归的方法另一种是递归的方法。

归并图解（盗图一张）：

归并排序的一般步骤为： 
1）将待排序数组（链表）取中点并一分为二； 
2）递归地对左半部分进行归并排序； 
3）递归地对右半部分进行归并排序； 
4）将两个半部分进行合并（mergeTwoLists）,得到结果。 

对应此题目，可以划分为三个小问题： 

1）写出middle函数，找到链表中点。（快慢指针思路，快指针一次走两步，慢指针一次走一步，快指针在链表末尾时，慢指针恰好在链表中点，见 带环链表 解析）

2）写出mergeTwoLists函数，即如何合并链表。 （见 合并两个排序链表 解析） 

3）写出sortList函数，实现上述步骤。

class Solution {  
public:  
       ListNode *sortList(ListNode *head) {  
        if(head ==NULL || head->next == NULL) return head;  
        ListNode* mid = middle(head);  
        ListNode* right = sortList(mid->next);//右边有序  
        mid->next = NULL;  
        ListNode* left = sortList(head);//左边有序  
        return mergeTwoLists(left,right);//将两个有序序列合并  
    }  
       
    //找到中间点  
    ListNode* middle(ListNode* head){  
        if(head==NULL) return NULL;  
        ListNode* slow = head;  
        ListNode* fast = head;  
        while(fast->next && fast->next->next)//注意，这与之前带环链表不同  
        {  
            slow = slow->next;  
            fast = fast->next->next;  
        }  
        return slow;  
    }  
  
    //合并两个有序链表  
    ListNode* mergeTwoLists(ListNode* left, ListNode* right){  
        if(left==NULL){    
            return right;    
        }else if(right==NULL){    
            return left;    
        }    
        ListNode *pMergeHead=NULL;    
         //取较小值作头结点    
        if(left->val<right->val){    
            pMergeHead=left;    
            left=left->next;    
        }else{    
            pMergeHead=right;    
            right=right->next;    
        }    
        ListNode *p=pMergeHead;////    
         //开始遍历合并    
        while(left!=NULL&&right!=NULL){    
            if(left->val<=right->val){    
                p->next=left;    
                left=left->next;    
                p=p->next;    
            }    
            else{    
                p->next=right;    
                right=right->next;    
                p=p->next;    
            }    
        }            
        if(left!=NULL)    
             p->next=left;    
        if(right!=NULL)    
             p->next=right;          
        return pMergeHead;    
    }  
};