92. Reverse Linked List II Leetcode Java

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.

Solution:

First of all, find the the (m-1)th node which will be the pre node of mth node. Start to reverse the list from m to n by inserting the current node between pre and pre.next and current will be updated to original current.next. Since m can be 1 which will be the head node so I use a preDummy node as usual to avoid the trouble of processing the head node specially.

 public ListNode reverseBetween(ListNode head, int m, int n) {  
     if(head==null || head.next==null || m==n) return head;  
     ListNode preDummy=new ListNode(0);  
     preDummy.next=head;  
     ListNode pre=preDummy;  
     for(int i=1;i<m;i++) pre=pre.next;  
     if(pre.next==null || pre.next.next==null) return head;  
     ListNode tail=pre.next;  
     for(int i=m+1;i<=n;i++){  
       ListNode cur=tail.next;  
       tail.next=cur.next;  
       cur.next=pre.next;  
       pre.next=cur;  
     }  
     return preDummy.next;  
   }