题解 | #牛群的重新排列#

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) {
        if (head == null || left == right) return head;
        ListNode node = new ListNode(-1);
        node.next = head;
        ListNode pre = node;

        // 将指针移动到需要反转的起始位置的前一个节点
        for (int i = 1; i < left; i++) pre = pre.next;
        ListNode start = pre.next;
        ListNode then = start.next;

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

        return node.next;
    }
}

知识点：链表的反转

使用语言：java

思路：

创建一个虚拟节点node，并将node的next指向头节点head，以便处理边界情况和统一操作。

初始化一个指针pre指向node，将pre移动到需要反转的起始位置的前一个节点。

初始化一个指针start，将start指向pre的下一个节点，即需要反转的起始节点。

初始化一个指针then，将then指向start的下一个节点。

使用循环，执行反转操作。循环次数为(right - left)次。

每次循环中，先将start的next指向then的next，保留then的下一个节点用于下一次循环。

然后将then的next指向pre的next，完成节点反转。

最后将pre的next指向then，完成当前节点的反转。

循环结束后，将反转后的链表和剩余的部分连接起来。

返回node.next，即反转后的链表头节点。

优化后的代码运行效率更好，减少了不必要的指针移动操作，简化了代码逻辑。

时间复杂度为O(n)，其中n为链表的长度。