经典链表排序题

• 链表排序最佳方案：归并排序
• 切分子链表时用快慢指针法找中点（注意fast初始位置非head）
• 递归终点为只剩一个节点（即!head->next），此时自然有序

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    ListNode* sortInList(ListNode* head) {
        /*
            1.链表排序的最佳选择：归并
            2.先归后并，归用递归，依次将链表切割为小链表
            3.归完要并，过程等价于合并两个有序链表
        */
        
        // 设计递归函数，经过该递归函数后链表变为有序
        return recursion(head);
        
    }
    
    ListNode* recursion(ListNode* head){
          // 确定递归终点
        if(!head->next)    // 只剩1个节点的时候递归结束，自然有序
            return head;
        
        // 找中点，每次递归划分成两个子链表
        // 用双指针总结帖中“快慢指针找中点”法
        ListNode* slow = head;
        ListNode* fast = head->next;
        while(fast && fast->next){
            slow = slow->next;
            fast = fast->next->next;
        }
        
        // 此时slow指针位于链表中点，分割子链表
        ListNode* mid = slow;
        ListNode* newHead = mid->next;
        mid->next = nullptr;
        
        // 归完要并
        return merge(sortInList(head),sortInList(newHead));
    }
    
    ListNode* merge(ListNode* p1, ListNode* p2){
        
        // 该函数用于合并两个有序链表
        ListNode* dummy = new ListNode(0);
        ListNode* cur = dummy;
        
        while(p1 && p2){
            if(p1->val <= p2->val){
                cur->next = p1;
                cur = cur->next;
                p1 = p1->next;
            }
            else{
                cur->next = p2;
                cur  = cur->next;
                p2 = p2->next;
            }
        }
        
        // 如果原链表节点个数为偶数，到上面就已经合并完了，如果是奇数，两个子链表p1和p2长度不同，需要将剩下的部分接上
        if(p1)
            cur->next = p1;
        if(p2)
            cur->next = p2;
        
        return dummy->next;
    }
};