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.

/**

public class Node {
int val;
Node next;
Node(int x) { val = x; }
}
**/

public class Solution {
public Node reverse(Node head, int m, int n) {

}
}

This problem is selected from LeetCode.

## Solution

The basic idea is first getting to the node at position m, and then reverse the n-m+1 nodes after, and relink the first part,
the reversed part and the third part of the list.

Be careful to some special cases:

When m = n, just return the original list.

When m = 1, remember to set head to the first node of the reversed list part.

public class Solution {
public Node reverse(Node head, int m, int n) {

Node mPrev = null;

// 1.move mCur to the correct
//   position of m
// 2.use mPrev to track the
//   previous node of mCur
while(--m > 0) {
mPrev = mCur;
mCur = mCur.next;

n--;
}

// 1.reverse the n-m+1 nodes
//   starting from mCur
// 2.use prev the track
//   the previous node of
//   the current node.
Node prev = null;
Node cur = mCur;
while(n-- > 0) {
Node next = cur.next;
cur.next = prev;
prev = cur;
cur = next;
}

// 1.now prev is the first node
//   of the reversed list part.
// 2.cur becomes the first node after the
//   reversed list part
// 3.mCur becomes the last node of the
//   reversed list part
// EX:
// x->x->mPrev mCur<-x<-x<-prev cur->x->null

// link the first part of
// the list to the start
// of the reversed list part
if(mPrev != null)
mPrev.next = prev;

// link the reversed list part
// to the third list part.
mCur.next = cur;

// if mCur is the original head,