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

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) {
        // write code here

        // 思路： 局部进行反转，也就是定位到需要反转的区间， 以反转的区间作为一个整体进行反转
        //        对反转区间，进行遍历头插的形式：
        //        1. 令pre为反转区间的头指针
        //        2. cur为反转区间游标
        //        3. cur_next指向cur下一个，防断链

        // 在java中对head，加上虚拟头结点，带头结点的链表操作不用考虑多种情况   
        ListNode T = new ListNode(0);
        T.next = head;
        ListNode pre = T;

        // 找到反转区间的头结点
        for(int i=0; i<m-1; i++){
            pre = pre.next;
        }

        // 分别为反转区间的游标，和游标下一个防止断链
        ListNode cur = pre.next;
        ListNode cur_next = null;

        

        // 将反转区间的结点反转
        for(int i=0; i<n-m; i++) { // 循环次数为反转区间的个数
            cur_next = cur.next;
            cur.next = cur_next.next;
            cur_next.next = pre.next;
            pre.next = cur_next;
        }

        return T.next;

    }
}

反转部分的过程图：