题解 | #牛的品种排序IV#

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

题目考察的知识点

这道题目考察的主要知识点是链表操作和排序。

题目解答方法的文字分析

我们需要对牛群进行排序，使得相同品种的牛相邻，并按照黑牛和白牛的顺序排列。我们可以使用分割链表的方法来实现。

思路步骤如下：

1. 分别创建两个新的链表，一个用来存放黑牛，一个用来存放白牛。
2. 遍历原链表，根据节点的值将节点加入对应的新链表中。
3. 将白牛链表连接到黑牛链表的尾部，这样就实现了黑牛在前，白牛在后的排序。
4. 返回新的链表。

本题解析所用的编程语言

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

完整且正确的编程代码

class Solution {
public:
    ListNode* sortCowsIV(ListNode* head) {
        if (!head || !head->next) {
            return head;
        }

        ListNode* blackHead = new ListNode(-1); // 伪头节点，用来存放黑牛
        ListNode* whiteHead = new ListNode(-1); // 伪头节点，用来存放白牛
        ListNode* blackTail = blackHead;
        ListNode* whiteTail = whiteHead;

        ListNode* current = head;
        while (current) {
            if (current->val == 0) {
                blackTail->next = current;
                blackTail = blackTail->next;
            } else {
                whiteTail->next = current;
                whiteTail = whiteTail->next;
            }
            current = current->next;
        }

        blackTail->next = whiteHead->next; // 将白牛链表连接到黑牛链表尾部
        whiteTail->next = nullptr; // 断开尾节点

        head = blackHead->next; // 新链表的头节点
        delete blackHead; // 释放伪头节点内存
        delete whiteHead; // 释放伪头节点内存

        return head;
    }
};

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