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

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) {
        ListNode fakeNode = new ListNode(-1);
        fakeNode.next = head;
        ListNode pre = fakeNode;

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

        ListNode cur = pre.next;
        ListNode next = null;
        for (int i = 0; i < n - m; i++) {
            next = cur.next;
            cur.next = next.next;
            next.next = pre.next;
            pre.next = next;
        }

        return fakeNode.next;
    }
}

思路完全参考一楼同学@X_fufu 的解题。过程对于我来说有些抽象，我就用自己的图解做分析。给有缘人跟我思维差不多的同学参考下。

关键点：

1) fake node 可以理解为整个过程唯一的不变节点，拿来最终返回用的。

2) cur 引用的节点不变，但是每轮一直右移一个节点。

3) 小箭头表示每轮循环需要做的唯一一件事情，就是把下一个节点放到pre.next 位置。

4) 大箭头表示next 属性每轮都因此要指向另外的节点。

容易犯的错误是，next.next = pre.next 而不是 cur, 尽管第一轮cur 跟 pre.next 相同，但是第二轮开始就变了。