148 链表归并排序

ListNode *merge(ListNode *l, ListNode *r) {
    auto *pRes = new ListNode(0);
    ListNode *temp = pRes;
    while (l != nullptr && r != nullptr) {
        if (l->val <= r->val) {
            temp->next = l;
            temp = temp->next;
            l = l->next;
        } else {
            temp->next = r;
            temp = temp->next;
            r = r->next;
        }
    }
    if (l != nullptr)
        temp->next = l;
    if (r != nullptr)
        temp->next = r;
    temp = pRes->next;
    delete pRes;
    return temp;
}

ListNode *mergeSort(ListNode *head) {
    if (head->next == nullptr)
        return head;
    ListNode *slow, *fast, *pre;
    slow = head;
    fast = head;
    pre = nullptr;
    while (fast != nullptr && fast->next != nullptr) {
        fast = fast->next->next;
        pre = slow;
        slow = slow->next;
    }
    pre->next = nullptr; //pre指向前半个链表的最后一个节点
    auto *l = mergeSort(head);
    auto *r = mergeSort(slow);
    return merge(l, r);
}


ListNode *sortList(ListNode *head) {
    if (head == nullptr || head->next == nullptr)
        return head;
    return mergeSort(head);
}