题解 | #牛群的身高排序#

与链表有关的题基本都是插入，删除，交换顺序等，解决这些问题通常将链表的指针进行修改。

问题分析：这道题本意就是对单链表进行排序，第一种方法就是新建一个结点，进行头插，遍历，比较，排序，时间复杂度为O(n^2)；第二种方法是**归并排序** ，归并排序说简单些就是将一堆n个数分成n个块，然后将n个块弄成大点的n/2个块，直到合成一个块。那么如何归并呢？会合并两个有序单链表吧，也会寻找单链表的中间结点吧，在这两个算法基础上就可以对单链表进行排序，时间复杂度为O(nlogn）。

本题解析所用的编程语言：c++

归并排序法：

//快慢指针寻找中间结点
ListNode* split(ListNode* head)
{
    ListNode* slow = head, * fast = head->next;

    while (fast != nullptr && fast->next != nullptr)
    {
        slow = slow->next;
        fast = fast->next->next;
    }

    ListNode* mid = slow->next;
    slow->next = nullptr;          //断尾

    return mid;
}
//合并两个有序链表
ListNode* mergeTwoLists(ListNode* head1, ListNode* head2)
{
    ListNode head(0), * p = &head;

    while (head1 != nullptr && head2 != nullptr)
    {
        if (head1->val < head2->val)
        {
            p->next = head1;
            head1 = head1->next;
        }
        else
        {
            p->next = head2;
            head2 = head2->next;
        }
        p = p->next;
    }
    //至少有一个链表为空，cur->next连接不为空的链表
    p->next = (head1 ? head1 : head2);

    return head.next;
}
ListNode* sortList(ListNode* head)
{
    // write code here
    if (head == nullptr || head->next == nullptr)
        return head;
    ListNode* head1 = head;
    ListNode* head2 = split(head);

    head1 = sortList(head1);
    head2 = sortList(head2);

    return mergeTwoLists(head1, head2);
}

头插法：

ListNode* sortList(ListNode* head)
{
    // write code here
    if (head == nullptr || head->next == nullptr)
        return head;

    ListNode newhead(-1);
    newhead.next = head;
    ListNode* cur = head->next; //用来遍历head链表
    ListNode* p1 = &newhead; //用来进行插入
    newhead.next->next = nullptr; //末尾结点指针置空
    while (cur)
    {
        while (p1->next && cur->val > p1->next->val)
            p1 = p1->next;

        ListNode* p2 = p1->next;
        p1->next = cur;
        ListNode* next = cur->next;
        cur->next = p2;
        cur = next;
        //插入完一个结点后，p1重新赋值
        p1 = &newhead;
    }
    return newhead.next;
}