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

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

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
        ListNode headBefore=new ListNode(0);
        headBefore.next=head;
        ListNode tempNode=head;
        ListNode rightStart;
        ListNode leftEnd,leftEndNext;
        
        //如果只有一个字母，返回该字母
        if(head.next==null){
            return head;
        }
        
        //确定leftEndNext
        if(m==1){
           leftEnd=headBefore;
        }else{
             for(int i=0;i<m-2;i++){
                tempNode=tempNode.next;
                }
            leftEnd=tempNode;
            tempNode=tempNode.next;
        }
        
        leftEndNext=leftEnd.next;
        //确定rightStatrt
        //此时tempNode指向需要反转链表的第一个Node
        int num=n-m+1;
        for(int i=0;i<num;i++){
            tempNode=tempNode.next;
        }
        rightStart=tempNode;
        leftEndNext=reverse(leftEndNext,num);
        tempNode=leftEndNext;
        leftEnd.next=leftEndNext;
        while(tempNode.next!=null){
            tempNode=tempNode.next;
        }
        tempNode.next=rightStart;
        return headBefore.next;
        
    }
    //反转
            public ListNode reverse(ListNode head,Integer num){
            ListNode tempNode=head;
            ListNode newHead=null;
            for(int i=0;i<num;i++){
                tempNode=head;
                head=head.next;
                tempNode.next=newHead;
                newHead=tempNode;
            }
            return tempNode;
        }

}