题解 | #牛群分隔#

题目考察的知识点：

本题主要考察链表数据结构和链表的基本操作。

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

为了实现链表的分隔操作，使得小于特定值 x 的节点在大于或等于 x 的节点之前，可以使用两个新链表来分别存放小于 x 和大于或等于 x 的节点。遍历原链表，将节点根据其值分别加入到这两个链表中，然后将两个链表连接起来。

本题解析所用的编程语言：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) {
        ListNode smallHead = new ListNode(0); // 创建小于x的链表头
        ListNode smallTail = smallHead; // 小于x的链表尾
        ListNode largeHead = new ListNode(0); // 创建大于等于x的链表头
        ListNode largeTail = largeHead; // 大于等于x的链表尾

        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; // 将大于等于x的链表尾的next置为null，避免链表成环

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