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

考察知识点：链表

题目分析：

可以新建两个头节点，一个是黑牛头节点，一个是白牛头节点。遍历一遍链表，将每个结点放到相应头节点所引领的链表之后即可。遍历完毕后需要将白牛链表插入到黑牛链表的末尾。

所用编程语言：C++

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    ListNode* sortCowsIV(ListNode* head) {
        // write code here
        ListNode blackH(-1);
        ListNode whiteH(-1);
        ListNode *p = &blackH;
        ListNode *q = &whiteH;
        while (head != nullptr) {
            if (head->val == 0) {
                p->next = head;
                p = p->next;
            }
            else {
                q->next = head;
                q = q->next;
            }
            head = head->next;
        }
        p->next = whiteH.next;
        q->next = nullptr;
        return blackH.next;

    }
};