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

该题考察的知识点：

• 链表的基本操作
• 链表节点值的分组

代码纲要：

1. 检查边界条件，如果链表为空或者只有一个节点，无需排序，直接返回链表头节点。
2. 创建两个哑节点，一个表示值为 0 的链表，一个表示值为 1 的链表，并初始化末尾节点指针。
3. 遍历原始链表，根据节点的值将其连接到对应的链表中，同时更新末尾节点指针。
4. 将值为 0 的链表的末尾指向值为 1 的链表的头部，并将值为 1 的链表的末尾设置为 null。
5. 返回排序后的链表头节点。

import java.util.*;

public class Solution {
    /**
     * 将链表中的节点按值 0 和 1 分组
     *
     * @param head 链表头节点
     * @return 排序后的链表头节点
     */
    public ListNode sortCowsIV(ListNode head) {
        // 如果链表为空或者只有一个节点，无需排序，直接返回链表头节点
        if (head == null || head.next == null) {
            return head;
        }

        // 创建两个哑节点，分别表示值为 0 的链表和值为 1 的链表
        ListNode zeroDummy = new ListNode(0);
        ListNode oneDummy = new ListNode(0);
        ListNode zeroTail = zeroDummy;  // 用于追踪值为 0 的链表的末尾节点
        ListNode oneTail = oneDummy;    // 用于追踪值为 1 的链表的末尾节点

        ListNode curr = head;
        while (curr != null) {
            // 根据节点的值将其连接到对应的链表中
            if (curr.val == 0) {
                zeroTail.next = curr;
                zeroTail = zeroTail.next;
            } else {
                oneTail.next = curr;
                oneTail = oneTail.next;
            }
            curr = curr.next;
        }

        // 将值为 0 的链表的末尾指向值为 1 的链表的头部，并将值为 1 的链表的末尾设置为 null
        zeroTail.next = oneDummy.next;
        oneTail.next = null;

        // 返回排序后的链表头节点
        return zeroDummy.next;
    }
}