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

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head ListNode类 第一段的头
     * @param m int整型 
     * @param n int整型 
     * @return ListNode类
     * 
     */
     static ListNode res_head=new ListNode(1001);
    public ListNode reverseBetween (ListNode head, int m, int n) {
        ListNode cur=head;
        ListNode head1=head;//要反向的头和尾
        ListNode tail1=head;
        ListNode tail2=null;//第一段的尾
        ListNode head3=null;//第三段的头
        int i=1;
        // write code here
        if(head.next==null){
            return head;
        }
        if(m==n){
            return head;
        }
        while(cur!=null){
            if(i+1==m){
                tail2=cur;//拿到第一段的尾
                head1=cur.next;//拿到反向的头
            }
            if(i==n){
                tail1=cur;//拿到反向的尾
                head3=cur.next;//拿到第三段的头
                tail1.next=null;//把反向的尾做成真的尾
            }
            cur=cur.next;
            i++;
        }
        //三段都拿到了
         head1=fun1(head1,n-m+1);
        if(tail2==null){
           head=head1;
        }else{
            tail2.next=head1;//把第二段反向，接在第一段后面
        }
        cur=head1;
        while(cur.next!=null){
            cur=cur.next;
        }//到这tail2就不要了，当作cur用去遍历，然后到第二段的尾。
        cur.next=head3;//然后接上第三段
        return head;
    }
    //这个是反向第二段的过程
        public ListNode fun1(ListNode cur,int length){
            if(length==1){
                return cur;
            }
            if(length==2){
                ListNode head=cur.next;
                cur.next.next=cur;
                cur.next=null;
                return head;
            }
            //比较长了再调用函数反向
            
            fun2(cur,cur.next);
            
            return res_head;
        }
        public static void fun2(ListNode node1,ListNode node2){
            if(node2.next!=null){
                fun2(node2,node2.next);
            }
            if(res_head.val==1001){
                res_head=node2;
            }
            node2.next=node1;
            node1.next=null;

        }

}