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

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类
     */
    public ListNode reverseBetween (ListNode head, int m, int n) {
        if(head == null || head.next == null || m==n){
            return head;
        }

        //创建一个虚节点
        ListNode dummy = new ListNode(-1);
        dummy.val = -1;
        dummy.next = head;

        //m位置的前一个节点
        ListNode ll = dummy,lr ,rl = dummy,rr;
        for(int i = 0; i< m-1; i++){
            ll = ll.next;
        }
        //m位置的节点
        lr = ll.next;

        //n位置的节点
        for(int i = 0; i< n; i++){
            rl = rl.next;
        }
        //n后一个节点
        rr = rl.next;

        rl.next = null;
        reverse(lr);
		
	  	//把反转后的连接起来
        ll.next = rl;
        lr.next = rr;

        return dummy.next;
    }

    public static void reverse(ListNode head){
        if(head == null){
            return;
        }

        ListNode pre = null, cur = head;
        while(cur != null){
            ListNode tmp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }
    }
}