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

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) {
        // write code here
        if (head == null)
            return null;
        ListNode dummy = new ListNode(0);	//用一个新的节点指向头节点，防止head这个节点也被返转了
        dummy.next = head;    
        ListNode prestart = dummy;   //用一个节点来记录m节点的前一个结点
        ListNode start = head;		//用一个结点来记录第m个结点
        for (int i = 1 ; i < m ; i++) {			//循环赋值
            prestart = start;
            start = start.next;
        }
	  /**
	  	*每次都把m结点的后面一个结点取出来 放到prestart的后面
		* 例如
		*1->2->3->4->5
		*1->3->2->4->5
		*1->4->3->2->5
		*/

        for (int i = 0 ; i < n - m ; i++) {
            ListNode next = start.next;
            start.next = next.next;
            next.next = prestart.next;
            prestart.next = next;
        }


        return dummy.next;
    }
}