题解 | #链表内指定区间反转#1找2反3连接

/*
 * 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
        if(head == null || head.next == null){
            return head;
        }
        //第一步 找到位置是m的节点 和 m的前一个节点preM
        ListNode mNode = head;
        ListNode preMNode = null;
        for(int i = 1; i < m;i++){
            if((i + 1) >= m){
                //最后一次循环
                preMNode = mNode;
            }
            mNode = mNode.next;
        }
        //第二步 从m节点开发翻转 n - m次 最后一次翻转同时完成首尾相连
        //翻转完以后 mNode就变成尾巴节点了
        ListNode tailNode = mNode;
        
        ListNode preNode = null;
        for(int i = 0; i <= n-m; i++){
            ListNode next = mNode.next;
            mNode.next = preNode;
            preNode = mNode;
           
            if(i == (n-m)){
                //最后一次执行
                if(preMNode != null){
                    preMNode.next = mNode;
                }
                tailNode.next = next;
            } else {
                mNode = next;
            }
        }
        if(m == 1){
            return preNode;
        } else {
            return head;
        }
    }
}