题解 | #链表内指定区间反转#

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 m int整型 
     * @param n int整型 
     * @return ListNode类
     */
    public ListNode reverseBetween (ListNode head, int m, int n) {
      if (m == n) {
            return head;
        }
        //因为可能涉及到操作原链表的头结点 使的头结点跟其他头结点的地位一样  不用进行额外的区分 所以设置虚拟头节点
        //比如如果翻转区间包含了原链表中的第一个位置,那么如果不设置dummy,在翻转过程中需要设置其他临时变量来保持第一位置的节点指针
        ListNode dummy = new ListNode(-1);

        //让虚拟节点指向原链表的头部
        dummy.next = head;

        //设置一个指针，指向以虚拟节点为链表的头部位置
        ListNode pre = dummy;

        //设置一个指针 指向原链表的头部位置
        ListNode cur = head;

        //从虚拟的头结点出发，pre 走 m-1步找到需要反转的左区间
        //for 循环结束后，pre的右节点是需要翻转的节点
        //for 循环结束后，pre指向的就是需要翻转的节点
        for (int i = 0; i < m - 1; i++) {
            //pre 不断的向右移动，直到走到翻转的左区间为止
            pre = pre.next;

            //cur 不断的向右移动，找到了需要翻转的第一个节点
            cur = cur.next;

        }

        //开始翻转这些节点
        for (int i = 0; i < n - m; i++) {

            //设置临时变量，保存当前需要翻转节点的后面的节点
            ListNode temp = cur.next;

            //这个时候让temp 和 cur 两个节点翻转一下
            //比如，一开始i=0的时候 cur 为2，temp为3
            //执行完下面的代码 如果原链是1 -> 2 -> 3 -> 4 -> 5
            //翻转后1 -> 3 -> 2 -> 4 -> 5

            //cur的下一个节点是等号右侧的值
            //i = 0的时候，cur为2，cur.next.next的值是4
            //等价于cur.next = temp.next
            cur.next = cur.next.next;

            //temp的下一个节点是当前pre.next的值
            //i = 0 时候 temp = 3,pre = 1,pre.next = 2
            //所以temp.next = pre.next
            temp.next = pre.next;

            //pre的下一节点是等号右侧的值
            //当i = 0 的时候,pre为1，temp的值是3
            //将pre指向下一个节点 也就是temp
            pre.next = temp;

            //i = 0 结束后 链表发生改变为
            //1 -> 3 -> 2 -> 4 -> 5
        }
        return dummy.next;
    }
}