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

题目考察的知识点：

这道题目主要考察了链表的基本操作以及按照特定规则进行排序的能力。

题目解答方法的文字分析：

我们需要将链表中的牛按照黑牛（0）和白牛（1）进行排序，使得相同品种的牛相邻，并按照黑牛和白牛的顺序排列。我们可以使用荷兰国旗问题的思想，维护两个虚拟节点分别代表黑牛和白牛，然后遍历原始链表，将牛按照品种连接到对应的虚拟节点后面。最后，将黑牛链表的末尾连接到白牛链表的开头，返回黑牛链表的头节点即可。

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

这个题解使用了Java编程语言。

完整且正确的编程代码：

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @return ListNode类
     */
    public ListNode sortCowsIV (ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode blackDummy = new ListNode(0); // Dummy node for black cows
        ListNode whiteDummy = new ListNode(0); // Dummy node for white cows
        ListNode blackPtr = blackDummy;
        ListNode whitePtr = whiteDummy;

        ListNode current = head;
        while (current != null) {
            if (current.val == 0) {
                blackPtr.next = current;
                blackPtr = blackPtr.next;
            } else {
                whitePtr.next = current;
                whitePtr = whitePtr.next;
            }
            current = current.next;
        }

        blackPtr.next = whiteDummy.next;
        whitePtr.next = null;

        return blackDummy.next;
    }
}