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

1. 题目考察的知识点

反转链表，区间反转

2. 题目解答方法的文字分析

方法主要是反转 left 到 right 部分以后，再拼接起来。为了实现拼接，我们还需要记录 left 的前一个节点，和 right 的后一个节点。 主要的实现步骤是

1、截取left到right的部分，然后将这部分从原来的链表截断 2、反转left到right的部分，将这部分拼接回原来链表 3. 本题解析所用的编程语言 java

4. 完整且正确的编程代码

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) {
          // 因为头节点有可能是需要翻转的子区间的一部分，所以建立虚拟的头节点dummy
        ListNode dummy = new ListNode(-1);
        dummy.next = head;

        ListNode pre = dummy;
        // 第 1 步：从虚拟头节点走 left - 1 步，来到 left 节点的前一个节点
        for (int i = 0; i < left - 1; i++) {
            pre = pre.next;
        }

        // 第 2 步：从 pre 再走 right - left + 1 步，来到 right 节点
        ListNode rightNode = pre;
        for (int i = 0; i < right - left + 1; i++) {
            rightNode = rightNode.next;
        }

        // 第 3 步：切断出一个子链表（截取链表）
        ListNode leftNode = pre.next;
        ListNode curr = rightNode.next;

        // 注意：切断链接
        pre.next = null;
        rightNode.next = null;

        // 反转链表的子区间
        reverse(leftNode);

        // 第 4 步：接回到原来的链表中
        pre.next = rightNode;
        leftNode.next = curr;
        return dummy.next;
    }

    private void reverse(ListNode head) {
        
        ListNode pre = null;
        ListNode cur = head;

        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
    }
    
}