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

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 (m == n) {
            return head;
        }
        ListNode front_front = m == 1 ? null : head;
        ListNode front;
        ListNode rear;
        int index = 0; //辅助查找front_front和rear的索引
        while (++index < m - 1) {
            front_front = front_front.next;
        }
        front = front_front == null ? head : front_front.next;
        rear = front.next;
        index = m;
        while (++index < n) {
            rear = rear.next;
        }
        if (front_front == null) {
            return overturn(front, rear.next);
        } 
        front_front.next = overturn(front, rear.next);
        return head;
    }


    private ListNode overturn(ListNode x, ListNode rear) {
        ListNode i = x;
        ListNode j = x.next;
        while (true) {
            if (j == rear) {
                x.next = rear;
                return i;
            }
            x.next = i;
            i = j;
            j = j.next;
            i.next = x.next;
        }
    }
}