Reverse Linked List II

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.

Hint: the idea of this problem is to correctly handle three parts of the linked list. Copy the first part (index<m), reverse the second part (m<=index<=n), and copy the last part. Pay attention to the cases that if(m==n), we do not need to reverse any nodes. Also, some cases may not have the first part or the third part.

01 public ListNode reverseBetween(ListNode head, int m, int n) {
02     // Start typing your Java solution below
03     // DO NOT write main() function
04     if(m==n||head==null ||head.next==null)
05         return head;
06     ListNode left=null;
07     ListNode leftEnd=null;
08     ListNode middle=null;
09     ListNode middleEnd=null;  
10   
11     //keep a pointer curr which walks step by step
12     ListNode curr=head;
13   
14     //handle the first part        
15     int i=1;
16     while( curr!=null && i<m)
17     {                      
18         if(left==null)
19         {
20             left=curr;
21             leftEnd=left;
22         }
23         else
24         {
25             leftEnd.next=curr;
26             leftEnd=leftEnd.next;
27         }
28         curr=curr. next;
29         i++;
30     }
31   
32     //handle the middle part: reverse
33     while(curr!=null && i<=n)
34     {          
35         ListNode temp=curr.next;
36         curr.next=middle;
37         middle=curr;  
38         //record the last node of the second part
39         if(middleEnd==null)
40         {                              
41             middleEnd=middle;
42         }  
43         curr=temp;
44         i++;
45     }
46   
47     //handle the last part
48     if(middleEnd!=null)
49     {
50         middleEnd.next=curr;
51     }
52   
53     if(left!=null )
54     {
55         leftEnd.next=middle;
56         return left;
57     }      
58     else
59     {
60         return middle;
61     }              
62 }