题解 | #牛群分隔#java

import java.util.*;

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

public class Solution {
    /**
     * 将链表中小于x的节点移到大于等于x的节点之前，并保持它们的相对位置。
     *
     * @param head 原始链表的头节点
     * @param x 特定值 x
     * @return 重排后的链表头节点
     */
    public ListNode cow_partition(ListNode head, int x) {
        // 创建两个新链表及其指针
        ListNode smallHead = new ListNode(0);
        ListNode smallTail = smallHead;
        ListNode largeHead = new ListNode(0);
        ListNode largeTail = largeHead;

        // 遍历原链表，将节点插入到对应的链表中
        while (head != null) {
            ListNode next = head.next;
            head.next = null;  // 断开 head 节点与原链表的连接

            if (head.val < x) {
                smallTail.next = head;
                smallTail = smallTail.next;
            } else {
                largeTail.next = head;
                largeTail = largeTail.next;
            }

            head = next;
        }

        // 将两个链表连接起来
        smallTail.next = largeHead.next;

        return smallHead.next;
    }
}

• 创建了两个新的链表：smallHead 和 largeHead。它们分别用作存储小于 x 的节点和大于等于 x 的节点。同时，我们还创建了指针 smallTail 和 largeTail 来分别指向两个链表的尾部。
• 遍历原始链表。对于每个节点，如果它的值小于 x，则将其插入到 smallTail 所指向的位置，并更新 smallTail；如果它的值大于等于 x，则将其插入到 largeTail 所指向的位置，并更新 largeTail。
• 在遍历过程中，不断更新原始链表的头节点 head，直到遍历完整个链表。
• 将大链表的尾部连接为 null，防止出现循环链表的情况。然后，将 smallTail 的下一个节点指向 largeHead 的下一个节点，完成链表的重排。
• 返回 smallHead 的下一个节点作为重排后的链表的头节点。

这样，就完成了链表的分割和重排。时间复杂度为 O(n)，其中 n 为链表的长度。

该题涉及的知识点包括链表、链表节点操作、指针操作和链表遍历。