题解 | #单链表的排序#

1.使用vec存储值，排序后构建新的链表

class Solution {
public:
	  /**
	   * 
	   * @param head ListNode类 the head node
	   * @return ListNode类
	   */
		ListNode* sortInList(ListNode* head) {
		//取巧的方法 52ms
        /*
        1.用 vector 先存储链表中各个节点的值
        2.使用 sort 对 vector 进行排序
        3.将 vector 中的值按顺序串联成新的链表
        */
        ListNode *res = new ListNode(0);
        ListNode *pre = res;
        vector<int> vec;
        while(head)
        {
            vec.push_back(head->val);
            head = head->next;
        }
        sort(vec.begin(),vec.end());
        for(int i = 0;i<vec.size();++i)
        {
            ListNode *node = new ListNode(vec[i]);
            pre->next = node;
            pre = pre->next;
        }
        return res->next;
	}
};

2. 使用归并排序，归并两个已经排序好的子表

具体做法：

step 1：首先判断链表为空或者只有一个元素，直接就是有序的。

step 2：准备三个指针，快指针fast每次走两步，慢指针slow每次走一步，前序指针pre每次跟在slow前一个位置。三个指针遍历链表，当快指针fast到达链表尾部的时候，慢指针slow刚好走了链表的一半，正好是中间位置。

step 3：从pre位置将链表断开，刚好分成两个子问题开始递归。

step 4：将子问题得到的链表合并

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

class Solution {
public:
    /**
     * 
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    //合并两个有序链表
    ListNode* merge(ListNode* pHead1,ListNode *pHead2)
    {
        if(!pHead1)
            return pHead2;
        if(!pHead2)
            return pHead1;
        ListNode *res = new ListNode(-1);
        ListNode *curr = res;
        while(pHead1 && pHead2)
        {
            if(pHead1->val <= pHead2->val)
            {
                curr->next = pHead1;
                curr = curr->next;
                pHead1 = pHead1->next;
            }
            else
            {
                curr->next = pHead2;
                curr = curr->next;
                pHead2 = pHead2->next;
            }
        }
        curr->next = pHead1?pHead1:pHead2;
        return res->next;
    }
	//排序 
    ListNode* sortInList(ListNode* head) {
        // write code here
        if(!head || !head->next)
            return head;
        ListNode *fast = head->next->next;
        ListNode *slow = head->next;
        ListNode *pre =  head;
        while(fast && fast->next)
        {
            fast = fast->next->next;
            slow = slow->next;
            pre = pre->next;
        }
        pre->next = nullptr;
        return merge(sortInList(head), sortInList(slow));
    }

};