单链表排序--归并排序

#include <iostream>
#include <cstdlib>
using namespace std;
struct ListNode //默认为public
{
    int data;
    ListNode* next;
    ListNode(int x, ListNode* nextNode):data(x), next(nextNode){}
};

ListNode* mergeData(ListNode* first, ListNode* second)
{
    if(first == nullptr) return second;
    if(second == nullptr) return first;
    //合并两个链表，按从小到大的顺序
    ListNode* new_head = new (nothrow) ListNode(0, nullptr); //分配失败返回空指针
    if(new_head == nullptr) exit(0);
    ListNode* ptr = new_head;
    while(first != nullptr && second != nullptr)
    {
        if(first->data < second->data)
        {
            ptr->next = first;
            first = first->next;
        }
        else
        {
            ptr->next = second;
            second = second->next;
        }
        ptr = ptr->next;
    }
    //合并剩余部分(对于数组进行归并排序，这部分可通过设置哨兵来省略)
    if(first != nullptr) ptr->next = first;
    if(second != nullptr) ptr->next = second;
    return new_head->next;
}

//返回为结点指针类型，需要链表头节点
ListNode* mergeSort(ListNode* head)
{
    //递归调用，首先找到分裂点，对于链表可以使用快慢指针方法
    if(head == nullptr || head->next == nullptr) return head;
    ListNode* fast = head->next;
    ListNode* slow = head;
    while(fast != nullptr && fast->next != nullptr)
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    //此时slow即为中间点,依次对slow之前的元素和之后的元素递归调用归并排序,然后进行合并
    ListNode* se = slow->next;
    slow->next = nullptr;
    ListNode* first = mergeSort(head);
    ListNode* second = mergeSort(se);
    return mergeData(first, second);
}

void printList(ListNode* head)
{
    if(head == nullptr) return;
    cout << head->data << " ";
    printList(head->next);
}

int main()
{
    ListNode* head =
        new ListNode(10, new ListNode(9, new ListNode(8, new ListNode(7, new ListNode(6, new ListNode(5, nullptr))))));
    printList(head);
    cout << endl;
    ListNode* new_head = mergeSort(head);
    printList(new_head);
    return 0;
}