Reverse Linked List II

Reverse a linked list from position m to n.

Have you met this question in a real interview? 

Yes

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.

Challenge

Reverse it in-place and in one-pass

/**

 * Definition for ListNode

 * public class ListNode {

 *     int val;

 *     ListNode next;

 *     ListNode(int x) {

 *         val = x;

 *         next = 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 head;

        ListNode preList = new ListNode(0);

        ListNode dummy = preList;

        preList.next = head;

        ListNode tempM = head;

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

            preList = tempM;

            tempM = tempM.next;

        }

        

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

            ListNode temp = tempM.next;

            tempM.next = temp.next;

            temp.next = preList.next;;

            preList.next = temp;

        }

        return dummy.next;

        

    }

}