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

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类
     */
    //想法就是遍历一遍完成。head作为遍历指针
    public ListNode reverseBetween (ListNode head, int m, int n) {      
		// 用一个新节点（两个作用）：
		// 保存头位置。保证链表分三段：前不变，中反转，后不变（null也是不变）
        ListNode out = new ListNode(0);
        out.next = head;
        ListNode tail0 = out;
        int index = 1;
		//找反转位置
        while(index<m){
            // 第一段尾
		    tail0 =head;
            head = head.next;
            index++;
        }
	    // 第二段尾
        ListNode tail1 = head;
        ListNode pre =null;
	  
        while(m<=index&&index<=n){
            ListNode temp = head.next;
            head.next =pre;
            pre = head;
            head =temp;
            index++;
        }
		// 第一段尾链接第二段头
        tail0.next = pre;
		// 第二段尾链接第三段头
        tail1.next =head;
        return out.next;
    }
}