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

知识点：链表

这道题目考查的还是链表反转问题，只不过需要我们自己确定需要反转的区间。具体来说，我们需要找到反转区间前后的两个节点，对于前面的节点来说，我们需要将其next指针指向我们反转后的结果；对于区间后面的节点来说，我们需要将区间第一个节点的next指针指向区间后面的第一个节点。

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(left == right) {
            return head;
        }
        ListNode preHead = new ListNode(-1);
        preHead.next = head;
        ListNode slow = preHead;
        for(int i = 1; i < left; i++) {
            slow = slow.next;
        }
        ListNode fast = slow.next;
        for(int i = left; i < right; i++) {
            fast = fast.next;
        }
        slow.next = reverse(slow.next, fast.next);
        return preHead.next;
    }

    private ListNode reverse(ListNode left, ListNode right) {
        ListNode pre = right;
        while(left != right) {
            ListNode tmp = left.next;
            left.next = pre;
            pre = left;
            left = tmp;
        }
        return pre;
    }
}