### 题目

Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example: Given 1->2->3->4->5->NULL, m = 2 and n = 4,

return 1->4->3->2->5->NULL.

Note: Given m, n satisfy the following condition: 1 ≤ m ≤ n ≤ length of list.

### in-place and in-one-pass, 复杂度$O(n)$

1. wall: 需要转动范围前的一个点，它是一个不动点，每次都插入在它后面。
2. right: 每次迭代向前插入的目标元素。
3. left: 目标元素right的前驱元素。

               wall      right(from)          right(to)
|         |------------------>|
sentinel -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9
|------------------>|
left(from)          left(to)


#### 代码

/**
* Definition for singly-linked list.
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode reverseBetween(ListNode head, int m, int n) {
if (m == n) { return head; }
ListNode sentinel = new ListNode(0), wall = sentinel;
for (int i = 1; i < m; i++) {
wall = wall.next;
ListNode left = wall.next, right = left.next; // right为要向前插的点，left是它的前一点
for (int i = m + 1; i <= n; i++) { // assert: n > m
left.next = right.next; //-|
right.next = wall.next; //-| >>> 这四步前插动作是本题的关键
wall.next = right;      //-|
right = left.next;      //-|
}
return sentinel.next;
}
}