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

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

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
        // 采用分段思路，分别找到 pre，left，right，next 4个节点
        // 添加一个虚节点，避免第一个节点的场景问题
        // pre.next 指向right,left.next 指向next
        ListNode root = new ListNode(-1);
        root.next = head;

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

        ListNode left = pre.next;
        ListNode right = left;

        for (int i = m; i < n; i++) {
            right = right.next;
        }

        ListNode next = right.next;

        pre.next = null;
        right.next = null;

        resever(left);

        pre.next = right;
        left.next = next;

        return root.next;
    }

    private void resever(ListNode head) {
        ListNode pre = null;
        ListNode next;

        while (head != null) {
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
    }
}