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

import java.util.*;
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) return null;

        // write code here


        //reverse between pre and after


        ListNode pre = new ListNode(-1);
        ListNode prefix = pre;
        pre.next = head;

        ListNode after = new ListNode(-1);
        after.next = head;

        for (int i = 1 ; i <= m - 1; i++) {
            pre = pre.next;
        }

        for (int i = 1 ; i <= n + 1; i++) {
            after = after.next;
        }

        reverse(pre, after);

        return prefix.next;
    }

    public void reverse(ListNode pre, ListNode after) {
        ListNode cur = pre.next;
        if (cur.next == after) return;

        ListNode next = cur.next;
        while (next != after) {
            ListNode preNext = next.next;
            next.next = cur;
            cur = next;
            next = preNext;
        }

        ListNode lisend = pre.next;
        ListNode lishead = cur;
        pre.next = cur;
        lisend.next = after;
    }
}