92. [M] Reverse Linked List II

依然是基于 206 的反转单链表。只是需要特别注意临界点的处理。

假设输入为 (1) -> (2) -> (3) -> (4) -> (5) ， M = 2 , N = 4 ，也就是反转 2、3 、4 三个节点。

​最初始的状态是

(p=null)  (1/c/head) -> (2) -> (3) -> (4) -> (5) -> (null)

然后向前移动 M-1 也就是 1 个元素，每次移动的时候更新 p 和 c ，结束之后成为如下状态

(1/p) -> (2/c/M) -> (3) -> (4/N) -> (5) -> (null)

这里是反转的起点。但是在开始之前，要记录一下 p 和 c ，因为最后反转完成之后，需要更新 t1 指向反转结果的首节点，更新 t2 指向反转段后一个节点。

(1/p/t1) -> (2/c/M/t2) -> (3) -> (4/N) -> (5) -> (null)

然后开始反转的过程

n = c.next
c.next = p
p = c
c = n

重复 M - N + 1 次，结果成为

第1次: (1/t1) <-> (2/p/M/t2) (3/c) -> (4/N) -> (5) -> (null)
第2次: (1/t1) <-> (2/M/t2) <- (3/p)  (4/c/N) -> (5) -> (null)
第3次: (1/t1) <-> (2/M/t2) <- (3) <- (4/p/N)  (5/c) -> (null)

反转结束，更新反转段的首尾指向

t1 指向 p: (1/t1) -> (4/p) -> (3) -> (2/t2)  (5/c) -> (null)
t2 指向 c: (1/t1) -> (4/p) -> (3) -> (2/t2) -> (5/c) -> (null)