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
        // 创建一个虚拟节点，用于存放小于x的节点
        ListNode lessNode = new ListNode(0);
        // 创建一个虚拟节点，用于存放大于等于x的节点
        ListNode greaterNode = new ListNode(0);
        // 指向小于x节点的指针
        ListNode lessPtr = lessNode;
        // 指向大于等于x节点的指针
        ListNode greaterPtr = greaterNode;

        while (head != null) {
            if (head.val < x) {
                lessPtr.next = head; // 将节点连接到lessNode后面
                lessPtr = lessPtr.next; // 移动指针
            } else {
                greaterPtr.next = head; // 将节点连接到greaterNode后面
                greaterPtr = greaterPtr.next; // 移动指针
            }
            head = head.next; // 遍历链表
        }

        greaterPtr.next =
            null; // 将大于等于x的节点的next指针置为null，断开与后面的节点的连接
        lessPtr.next =
            greaterNode.next; // 将小于x的节点的next指针指向大于等于x的节点，完成分隔

        return lessNode.next; // 返回分隔后的链表头节点
    }
}

该题考察的知识点包括：

1. 单链表的遍历和操作：需要对链表进行遍历，根据节点的值将节点连接到两个不同的链表中。
2. 虚拟节点的使用：通过创建虚拟节点来简化代码，避免对头节点进行特殊处理。
3. 指针的移动：通过移动指针来连接节点，并在遍历过程中更新指针的位置。
4. 边界条件处理：需要考虑链表为空的情况。

代码解释：

• 检查特殊情况：如果链表为空或n小于等于1，则直接返回原链表头节点。
• 使用快慢指针的思想，初始化两个指针slow和fast，它们都指向链表的头节点。
• 快指针fast先移动n个节点。如果快指针已经到达链表的末尾，说明需要移动的是头节点，直接返回原链表头节点的下一个节点。
• 当快指针fast没有到达链表末尾时，快慢指针同时移动，直到快指针到达链表末尾。此时，慢指针slow指向倒数第n+1个节点，也就是需要移动的倒数第n个节点的前一个节点。
• 将倒数第n个节点从链表中剥离出来，并将slow.next指向剩余部分的起始节点。
• 根据是否移动了头节点，返回原链表的头节点或新的头节点。