ReverseLinkedListII.java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class ReverseLinkedListII{
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if (head == null) return null;

        // get the node at position m minus 1;
        ListNode nodeMM1 = findNodeAtMMinusOne(head, m);
        
        // get the node at position m
        ListNode nodeM = current;
        ListNode current = nodeMM1.next;
        // later also get the node at position at n + 1;
        
        // reverse the node from m to n;
        int i = 0;
        ListNode nextNode = null;
        ListNode previous = null;
        while (i < n - m){ // here might be buggy, could nodeM be null already?
            nextNode = current.next;
            current.next = previous;
            previous = current;
            current = nextNode;
            i++;
        }
        // right now current is at node(n) but we haven't done the reverse yet
        // set node(m-1).next = node(n);
        nodeMM1.next = current;
        
        // reverse node(n)
        nextNode = current.next;
        current.next = previous;
        previous = current;
        current = nextNode;
        
        // right now current is at node(n+1)
        // set node(m).next = node(n+1);
        nodeM.next = current;
        // return the head;
        if(m == 1) head = nodeMM1.next;
        return head;
    }
    
    private ListNode findNodeAtMMinusOne(ListNode head, int m){
        int i = 1;
        ListNode nodeMM1 = null;
        ListNode current = head;
        while(i < m-1){ // be careful about the index. in the question the index start with 1
            current = current.next;
            i++;
        }
        nodeMM1 = current;
        if(m == 1) { // then we create a sentinel node at the beginning
            nodeMM1 = new ListNode(-1);
            nodeMM1.next = head;
        }
        return nodeMM1;
    }
}