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

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
        int index = 1;
        ListNode lastNode = null;
        ListNode curNode = head;
        ListNode childNodeHead = null;
        //1,2,3,4,5
        //m=2,n=4
        while(curNode != null){
            if(index == m){
                //当遍历到m点时，传递此时的结点
                //2->3->4->5->null,4-2+1=3
                childNodeHead = reverse(curNode, n-m+1);
                break;
            }
            lastNode = curNode;
            curNode = curNode.next;
            index ++;
        }
        if(lastNode!=null){
            //这个last，是1，将1传给得到的子链
            lastNode.next = childNodeHead;
        }else{
            //如果没有前，说明从第一个结点就开始反转了
            head = childNodeHead;
        }
      
        return head;
    }

    //这个方法，将head结点，指定长度为length，反转，且原来的头，指向原来的尾部的后一个结点
    //head:2->3->4->5->null length:3
    public ListNode reverse(ListNode head, int length){
    
        ListNode cur = head;
        ListNode tmp = null;
        ListNode last = null;
    
        for(int i=0;i<length;i++){
            //第一遍循环              //第二遍循环
            //cur=2,last=null,tmp=3 //cur=3,last=2,tmp = 4
            tmp = cur.next;
            // null<-2 3->4->5->null//null<-2<-3 4->5->null   
            cur.next = last;
            // last 2.              //last 3
            last = cur;
            // cur 3                //cur
            cur = tmp;
        }

        //循环之后
        //null<-2<-3<-4 5->null last=4,tmp=5
        head.next = tmp;

        // null<-5<-2<-3<-4
        //把4传回去
        return last;
    }

}