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

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
        //定义一个虚拟头结点比较好
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        //定义节点指针
        ListNode pre = dummy;
        ListNode cur = head;
        ListNode temp1 = null;//区间的前一节点
        ListNode temp2 = null;//区间的下一节点   
        ListNode temp4 = null;//区间的左端节点
        int i;

        if(m==n){
            return head;
        }
        for(i=0; i<m; i++){
            if(m==1){
                temp1 = pre;
            }else if(i==m-1){
                temp1 = pre;//保存区间的前一节点
            }  

            pre = pre.next;
            cur = cur.next;
            if(i==m-1){
                temp4 = pre;//保存区间的左端节点
                int k=0;
                while(k<=n-m-1){
                    ListNode temp = cur.next;
                    cur.next = pre;
                    pre = cur;
                    cur = temp;
                    k++;
                }
            }
            //pre为区间的右端节点
            temp2 = cur;//保存区间的下一节点      
        }
        temp1.next = pre;//区间的前一节点指向区间的右端节点
        temp4.next = cur;//区间的左端节点指向区间的下一节点

        return dummy.next;
    }
}