题解 | #单链表的排序#

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
    ListNode* merge(ListNode* p1, ListNode* p2){
        ListNode* dummy = new ListNode(-1);
        ListNode* p = dummy;
        while(p1 && p2){
            if(p1->val < p2->val){
                p->next = p1;
                p1 = p1->next;
            }else{
                p->next = p2;
                p2 = p2->next;
            }
            p = p->next;
        }
        p->next = p1==nullptr ? p2 : p1;
        return dummy->next;
    }
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    ListNode* sortInList(ListNode* head) {
        // 若表头为空，或者只有一个节点，直接返回
        if(head==nullptr || head->next==nullptr)    return head;
        ListNode* fast = head, *slow = head, *pre;
	   // 归并排序，找中间分割点
        while(fast!=nullptr && fast->next!=nullptr){
            pre = slow;
            fast = fast->next->next;
            slow = slow->next;
        }
        pre->next = nullptr;
        // 归并排序，自底向上
        return merge(sortInList(head), sortInList(slow));
    }
};