12.2 Reverse Linked List II (Between) - Medium

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.

https://leetcode.com/problems/reverse-linked-list-ii/

http://bangbingsyb.blogspot.com/2014/11/leetcode-reverse-linked-list-ii.html

public class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
         if(head==null||m>n||m<1)return head;

         ListNode dummy=new ListNode(0);
         dummy.next=head;
         head=dummy;     //Dummy=head=0 1 2 3 4 5 6 7 8 9

         // move head to (m-1)th node
         for(int i=0;i<m-1;i++)head=head.next;   //head = 3 4 5 6 7 8 9

        // reverse list from pre with length n-m+1
        // same as (12.1 Reverse Linked List)
         ListNode previous=head.next;
         ListNode cur=previous.next;
         ListNode next=null;

         for(int i=0;i<n-m;i++){ //pre = 6 5 4 (reversed)
             next=cur.next;      //cur = 7 8 9
             cur.next=previous;
             previous=cur;
             cur=next;
         }
         head.next.next=cur;   //head =      3     4     ,7 8 9
         head.next=previous;   //head =      3 , 6 5 4    ,7 8 9

         return dummy.next;     //Dummy= 1 2 3   6 5 4   7 8 9 
    }
}