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.

ListNode.java

package com.interviewbytes.linkedlists;

public class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}

ReverseBetween.java

package com.interviewbytes.linkedlists;

public class ReverseBetween {

    public ListNode reverseBetween(ListNode head, int m, int n) {

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

        ListNode prev = sentinel;

        int index = 0;

        while (index < m - 1) {
            prev = prev.next;
            index++;
        }

        ListNode current = prev.next;
        ListNode start = prev.next;

        ListNode reverse = null;

        while (index < n) {
            ListNode next = current.next;
            current.next = reverse;
            reverse = current;
            current = next;
            index++;
        }

        prev.next = reverse;
        start.next = current;


        return sentinel.next;
    }
}