Reverse a linked list from position m to n.

Notice

Given m, n satisfy the following condition: 1 ≤ m ≤ n ≤ length of list.

Have you met this question in a real interview?

Yes

Example

Given1->2->3->4->5->NULL, m =2and n =4, return1->4->3->2->5->NULL.

public class Solution {
    /**
     * @param ListNode head is the head of the linked list 
     * @oaram m and n
     * @return: The head of the reversed ListNode
     */
    public ListNode reverseBetween(ListNode head, int m , int n) {
        // write your code
        if (head == null) {
            return null;
        }

        ListNode dummy = new ListNode(0);
        dummy.next = head;
        head = dummy;


        //1->2->3->4
        for (int i = 1; i < m; i++) {
            head = head.next;
        }

        ListNode preM = head;
        ListNode mNode = head.next;
        ListNode nNode = mNode;
        ListNode postNNode = mNode.next;

        for (int i = m; i < n; i++) {

            ListNode temp = postNNode;
            postNNode = postNNode.next;
            temp.next = nNode;
            nNode = temp;

        }

        mNode.next = postNNode;
        preM.next = nNode;

        return dummy.next;

    }
}