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

知识点：

1. 单链表的遍历与操作。
2. 反转链表中给定范围的节点。

题意分析：

题目描述了一个链表，表示农场里的牛，节点的值为牛的编号。农场主想要改变牛群的排列顺序，要求反转从位置 left 到位置 right 的链表节点，并返回反转后的牛群链表。

时间复杂度：

假设链表中有N个节点。

1. 在代码中，我们需要遍历链表找到需要反转的部分，并使用栈辅助反转。在最坏情况下，需要遍历整个链表一次，这需要O(N)的时间复杂度。
2. 因此，总的时间复杂度为O(N)。

代码分析：

代码中的解决思路是遍历链表找到需要反转的部分，使用栈辅助进行反转。具体的步骤如下：

1. 创建一个临时指针tmp用于遍历链表。
2. 创建一个左子链表l用于保存给定范围左边的链表，同时创建一个左子链表头节点ll。
3. 创建一个中子链表mid用于保存给定范围内需要翻转的子链表，同时创建一个中子链表头节点mmid。
4. 创建一个栈stack用于辅助反转。
5. 遍历链表，首先将链表的左边部分（左子链表）添加到l，并将tmp指针移动到需要翻转的子链表的起始位置（left节点处）。
6. 然后，将需要翻转的子链表中的节点值依次压入栈中。
7. 接着，依次从栈中弹出节点值，构建中子链表，并将mid指针移动到中子链表的尾部（right节点处）。
8. 将左子链表的尾节点与中子链表的头节点连接起来。
9. 将中子链表的尾节点与后面的链表连接起来。
10. 最后，返回反转后的链表头节点ll.next。

代码：

import java.util.*;

class ListNode {
    int val;
    ListNode next;

    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) {
        ListNode tmp = head; // 临时指针，用于遍历链表
        ListNode l = new ListNode(-1); // 左子链表，表示给定范围左边的链表，随tmp移动的节点，定义左子链表右边界
        ListNode ll = l; // 左子链表头节点，表示：[-1 -> 节点1]
        ListNode mid = new ListNode(-1); // 中子链表，表示给定范围内需要翻转的子链表，随tmp移动的节点，定义中子链表右边界
        ListNode mmid = mid; // 中子链表头节点，表示：[-1 -> 节点1]
        Stack<Integer> stack = new Stack<>(); // 使用栈辅助反转

        while (head != null) {
            // 将链表的左边部分（左子链表）添加到l
            for (int i = 1; i < left; i++) {
                ListNode p = new ListNode(tmp.val);
                p.next = null;
                l.next = p;
                l = p;
                tmp = tmp.next;
            }

            // 将需要翻转的子链表中的节点值依次压入栈中
            for (int i = 0; i < right - left + 1; i++) {
                stack.push(tmp.val);
                tmp = tmp.next;
            }

            // 依次从栈中弹出节点值，构建中子链表
            for (int i = 0; i < right - left + 1; i++) {
                ListNode p = new ListNode(stack.pop());
                p.next = null;
                mid.next = p;
                mid = p;
            }
            break;
        }
        l.next = mmid.next; // 将左子链表的尾节点与中子链表的头节点连接
        mid.next = tmp; // 将中子链表的尾节点与后面的链表连接
        return ll.next; // 返回反转后的链表头节点
    }
}