题解 | #牛群的重新排列#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 left int整型 
     * @param right int整型 
     * @return ListNode类
     */
    public ListNode reverseBetween (ListNode head, int left, int right) {
        // write code here
 if (head == null || left == right) {
            return head;
        }

        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode pre = dummy;

        // 找到反转的起始位置前一个节点
        for (int i = 1; i < left; i++) {
            pre = pre.next;
        }

        // 反转的起始位置节点
        ListNode start = pre.next;
        ListNode curr = start.next;

        // 反转链表节点
        for (int i = left; i < right; i++) {
            start.next = curr.next;
            curr.next = pre.next;
            pre.next = curr;
            curr = start.next;
        }

        return dummy.next;
    }
}

定义了链表节点的类 ListNode。

创建了一个方法 reverseBetween，用于反转从位置 left 到位置 right 的链表节点。

在 reverseBetween 方法中，我们首先创建一个哑节点 dummy，并将其指向头节点。这样可以方便处理需要反转的起始位置在链表开头的情况。

定义指针 pre 指向反转的起始位置前一个节点。通过循环找到反转的起始位置前一个节点。

定义指针 start 指向反转的起始位置节点，并定义指针 curr 指向下一个要反转的节点。

通过循环将链表中从位置 left 到位置 right 的节点进行反转。具体操作如下：

• 将 start.next 指向 curr.next，断开反转范围内当前节点与后续节点的连接。
• 将 curr.next 指向 pre.next，将当前节点插入到反转范围内起始位置的前面。
• 将 pre.next 指向 curr，将前一个节点指向当前节点。
• 更新指针 curr 到下一个要反转的节点。

最后，返回哑节点 dummy 的下一个节点，即为反转后的链表的头节点。

该题的主要知识点是链表的反转。链表是一种常见的数据结构，它由多个节点组成，每个节点包含一个值和一个指向下一个节点的指针。在这道题中，我们需要反转链表中从位置 left 到位置 right 的节点。