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

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类
     */
     //方法1：新建链表,然后抽取利用栈反转(时间复杂度O(n) 空间复杂度O(n))//不做详细解释n虽然空间复杂度是O（1），但其实当m-n近似为链表长度时，所用空间复杂度最大为n,由等差数列就能得到平均空间复杂度为O(n);
     //方法2；直接遍历过程中插入反转(时间复杂度O(n) 空间复杂度O(1))
    public ListNode reverseBetween (ListNode head, int m, int n) {
        // write code here
        //设置虚拟结点
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        //找到m位置的前驱结点pre作为定点
        ListNode pre = dummy;
        for(int i = 0; i<m-1; i++){   //i设置为0其实为了与虚拟结点dummy同步，更易理解
            pre = pre.next;
        }

        ListNode headre = pre.next;   //headre也为定点，表明需要反转的链表的头结点
        ListNode headre_next = headre.next;   //为headre_next为headre的后继节点
        for(int i=0; i<n-m;i++){
            headre.next = headre_next.next; 
            headre_next.next = pre.next;      //pre.next不能换成cur，因为这两个只有第一次地址是一样的
            pre.next = headre_next;
            headre_next = headre.next;     
        }
        return dummy.next;
    }

}