题解 | #牛群分隔#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类
     * @param x int整型
     * @return ListNode类
     */
    public ListNode cow_partition (ListNode head, int x) {
        // write code here
        // 创建两个新链表及其指针
        ListNode smallHead = new ListNode(0), smallTail = smallHead;
        ListNode largeHead = new ListNode(0), largeTail = largeHead;

        // 遍历原链表，将节点插入到对应的链表中
        while (head != null) {
            if (head.val < x) {
                smallTail.next = head;
                smallTail = smallTail.next;
            } else {
                largeTail.next = head;
                largeTail = largeTail.next;
            }
            head = head.next;
        }

        // 将两个链表连接起来
        largeTail.next = null;  // 将 large 链表的尾部连接为 null，防止出现循环链表
        smallTail.next = largeHead.next;

        return smallHead.next;
    }
}

该题涵盖的知识点包括：

1. 链表：链表是一种常见的数据结构，由一系列节点组成，每个节点包含一个值和一个指向下一个节点的指针。链表可以用来存储和操作动态数据集合。
2. 链表节点插入：通过更改节点之间的指针关系，可以在链表中插入新的节点。在题目中，根据特定值 x，需要将小于 x 的节点插入到大于或等于 x 的节点之前。
3. 虚拟头节点：为了方便处理链表的头部，可以引入一个虚拟头节点。在题目中，创建了两个新链表 smallHead 和 largeHead，它们都有一个虚拟头节点，初始时它们的尾指针指向虚拟头节点。
4. 指针操作：通过移动指针，可以在链表中进行节点的遍历、插入和连接操作。在题目中，使用两个指针 smallTail 和 largeTail 来记录 small 链表和 large 链表的尾部位置，通过更新这些指针来插入节点和连接链表。

定义了一个 ListNode 类，用于表示链表节点，包含一个整数值和一个指向下一个节点的指针。另外还定义了一个 Solution 类，其中包含一个方法 partition，用于分隔链表。

具体步骤如下：

1. 创建两个新链表 smallHead 和 largeHead，以及它们对应的尾指针 smallTail 和 largeTail。初始时，两个新链表只有一个虚拟头节点，并且尾指针指向该虚拟头节点。
2. 遍历原链表 head，对于每个节点：如果节点的值小于特定值 x，则将节点插入到 small 链表中，更新 smallTail 指针和 smallTail 的下一个指针。如果节点的值大于等于特定值 x，则将节点插入到 large 链表中，更新 largeTail 指针和 largeTail 的下一个指针。
3. 将 large 链表的尾部连接为 null，防止出现循环链表。
4. 将 small 链表的尾部指向 large 链表的头部。
5. 返回 small 链表的头节点。

可以将链表按照特定值分隔成两部分，小于特定值的节点在前面，大于等于特定值的节点在后面，同时保留了每个节点的初始相对位置。该算法的时间复杂度为 O(N)，其中 N 是链表中的节点数目。