# AUG!!! Solution in JAVA, Clean Structure with Clean EXPLAINATION

• ``````/**
* General Idea: eg.1->2->3->4->5 and m = 2 n = 4
* We want to get 1 ->4->3->2->5
* We can find out that we need to do two things,
*  1 keep the order of nodes out of range [2,4]
*  2 reverse the order of nodes in position [2,4]
*  To do that, we need three new nodes to mark the position of nodes including
*  the previous node(m - 1) before position m, the first node(n) in range [m,n]
*  and the last node[n] in range[m,n]
*  After doing that, we can redirect the next of  previous node to last,
* next of first node to last's next And then, reverse the order between [m, n]
*/
public class Solution {
public ListNode reverseBetween(ListNode head, int m, int n) {
ListNode first = null;
ListNode last = null;
ListNode pre = null;
ListNode hd = head;//Always copy a head for later use in ListNode preblem

for(int i = 1; i <= n; i++)
{
if(i == m - 1)//find the previous node
pre = hd;

else if(i == m)//find the first node
first = hd;

if(i == n)//find the last node, it does not matter if n == m
{
last = hd;
break;//   after finding the last node, we can stop
}

hd = hd.next;//move to next
}

ListNode curr = first.next;
if(pre == null)//if pre == null, which means m == 1, the head node after reverse should be the last node in [m,n]
else//if pre != null head is the same with the original list
pre.next = last;

first.next = last.next;
for(int i = 0; i < n - m; i++)//The following is to reverse the order between [m,n]
{
ListNode next = curr.next;
curr.next = first;
first = curr;
curr = next;
}