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

考察知识点： 链表、链表取中点、归并排序、链表合并

题目分析：

 题目要求对一个链表进行排序。可以使用归并排序的方法，每次找到链表的中点，以此作为分界点，将该点左边（包括该点）与右边这两个子问题分别看成一个完成的排序问题（调用sortList）进行排序。因为sortList函数返回值应该是排序好的链表的头节点，只需要将两个排好序的链表合并即可。

 例如{5,9,2,7,3}

 注意用双指针找到的中点，如果链表是偶数，那么中点索引恰好是链表中结点数的一半。如果链表是奇数，那么中点索引是中间的节点，而不是length / 2这样的向0取整。

 分成这样的子问题后，从底部归并即可得到原问题的解。

所用编程语言： C++

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    ListNode* getMid(ListNode* head) {
        ListNode node(-1);
        node.next = head;
        ListNode *slow = &node, *fast = &node;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }

    ListNode *merge(ListNode *left, ListNode *right) {
        ListNode head(-1);
        ListNode *p = &head;
        while (left && right) {
            if (left->val <= right->val) {
                p->next = left;
                p = p->next;
                left = left->next;
            } else {
                p->next = right;
                p = p->next;
                right = right->next;
            }
        }
        if (left) p->next = left;
        if (right) p->next = right;
        return head.next;
    }

    ListNode* sortList(ListNode* head) {
        // write code here
        if (!head || !head->next) return head;
        ListNode *mid = getMid(head);
        ListNode *j = mid->next;
        mid->next = nullptr;
        ListNode *left = sortList(head);
        ListNode *right = sortList(j);
        return merge(left, right);
    }
};