LeetCode 92. Reverse Linked List II (Problem: https://leetcode.com/problems/reverse-linked-list-ii) - 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.

ReverseLinkedListII.java

/**
 * LeetCode 92. Reverse Linked List II (Problem: https://leetcode.com/problems/reverse-linked-list-ii)
 * 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.
 */


/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
 
public class ReverseLinkedListII {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if(head == null) return null; // Empty list
        if(head.next == null) return head; // Linked list with one element
        if(m == n) return head; // Nothing to swap
        
        // Create a dummy element to save head
        ListNode safeHead = new ListNode(-1);
        safeHead.next = head;
        
        // Create another dummy element to point to head
        ListNode leftBound = new ListNode(-1);
        leftBound.next = head;
        
        /** 
        * Initialize two more pointers pointing to two ListNodes 
        * immediately following head respectively
        */
        ListNode rightBound = leftBound.next;
        ListNode swapNode = rightBound.next;
        
        /**
        * Position all pointers as follows:
        * leftBound => (m-1)th element
        * rightBound => mth element
        * swapNode => (m+1)th element
        *
        * Example Run: 
        * 1->2->3->4->5->6->7, m=2, n=5
        * After all iterations of the for loop below: 
        * leftBound => 1, rightBound => 2, swapNode => 3.
        */
        for(int i = 1; i < m; i++){
            leftBound = leftBound.next;
            rightBound = rightBound.next;
            swapNode = swapNode.next;
        }
        
        /**
        * IMPORTANT:
        * If m = 1, that means head is going to move.
        * In this case, after positioning the pointers save the head again.
        */
        if(rightBound == head) safeHead = leftBound;
        
        /**
        * Using leftBound and rightBound as boundaries, keep inserting nodes
        * in reverse order between leftBound and rightBound for (n-m) iterations.
        * 
        * Example Run: 
        * 1->2->3->4->5->6->7, m=2, n=5
        * Before running the for loop below, leftBound => 1, rightBound => 2, swapNode => 3.
        * After first iteration, leftBound => 1, rightBound => 2, swapNode => 4 and list is 1->3->2->4->5->6->7
        * After second iteration, leftBound => 1, rightBound => 2, swapNode => 5 and list is 1->4->3->2->5->6->7
        * After third iteration, leftBound => 1, rightBound => 2, swapNode => 6 and list is 1->5->4->3->2->6->7
        * Stop.
        */
        int noOfIterations = n - m; // Not really necessary to separately store result, but used here for readability
        for(int j = 0; j < noOfIterations; j++){
            rightBound.next = swapNode.next;
            swapNode.next = leftBound.next;
            leftBound.next = swapNode;
            swapNode = rightBound.next;
        }
        
        return safeHead.next;
    }
}