题解 | #单链表的排序#

使用归并排序。

class Solution {
  public:
    ListNode* sortInList(ListNode* head) {
        // write code here
        if (head == nullptr) {
            return nullptr;
        }
        if (head->next == nullptr) {
            return head;
        }
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast != nullptr && fast->next != nullptr &&
                fast->next->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
        }
        auto p = slow->next;
        slow->next = nullptr;
        return Merge(sortInList(head), sortInList(p));
    }

    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        // write code here
        if (pHead1 == nullptr) {
            return pHead2;
        }
        if (pHead2 == nullptr) {
            return pHead1;
        }
        ListNode* head;
        if (pHead1->val < pHead2->val) {
            head = pHead1;
            pHead1 = pHead1->next;
        } else {
            head = pHead2;
            pHead2 = pHead2->next;
        }
        ListNode* p = head;
        while (pHead1 != nullptr && pHead2 != nullptr) {
            if (pHead1->val < pHead2->val) {
                p->next = pHead1;
                p = p->next;
                pHead1 = pHead1->next;
            } else {
                p->next = pHead2;
                p = p->next;
                pHead2 = pHead2->next;
            }
        }
        if (pHead1 == nullptr && pHead2 != nullptr) {
            p->next = pHead2;
        } else if (pHead1 != nullptr && pHead2 == nullptr) {
            p->next = pHead1;
        } else {
            p->next = nullptr;
        }
        return head;
    }
};