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

大家好，我是开车的阿Q，自动驾驶的时代已经到来，没时间解释了，快和阿Q一起上车。作为自动驾驶系统工程师，必须要有最好的C++基础，让我们来一起刷题吧。

题目考察的知识点

这道题目考察了链表的排序，可以使用归并排序来解决。

题目解答方法的文字分析

归并排序的思想是将链表不断分成两半，对每一半进行排序，然后再将两个有序的链表合并成一个有序的链表。

具体操作可以分为以下步骤：

1. 使用快慢指针找到链表的中间节点，将链表分成两部分。
2. 递归调用sortList函数对左半部分和右半部分分别排序。
3. 编写一个辅助函数用于合并两个有序链表，将其合并成一个有序链表。
4. 最后，返回合并后的链表。

本题解析所用的编程语言

本题解析所用的编程语言为C++。

完整且正确的编程代码

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    ListNode* sortList(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return head; // 链表为空或只有一个节点，已经有序
        }
        
        ListNode* mid = findMiddle(head); // 找到链表的中间节点
        ListNode* right = mid->next;
        mid->next = nullptr; // 断开链表
        
        ListNode* sortedLeft = sortList(head); // 递归排序左半部分
        ListNode* sortedRight = sortList(right); // 递归排序右半部分
        
        return merge(sortedLeft, sortedRight); // 合并两个有序链表
    }
    
    ListNode* findMiddle(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast->next != nullptr && fast->next->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
    
    ListNode* merge(ListNode* l1, ListNode* l2) {
        if (l1 == nullptr) {
            return l2;
        }
        if (l2 == nullptr) {
            return l1;
        }
        
        if (l1->val < l2->val) {
            l1->next = merge(l1->next, l2);
            return l1;
        } else {
            l2->next = merge(l1, l2->next);
            return l2;
        }
    }
};

在这个代码中，我们使用归并排序的思想对链表进行排序，先找到链表的中间节点，然后递归对左右两部分进行排序，最后合并两个有序的链表。

您的关注、点赞、收藏就是我创作的动力，三连支持阿Q！