92. Reverse Linked List II

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    private ListNode reverseN(ListNode head, int n) {
        ListNode prev = null;
        ListNode curr = head;
        for (int i = 0; i < n; i++) {
            ListNode oldNext = curr.next;
            curr.next = prev;
            prev = curr;
            curr = oldNext;
        }
        return prev;
    }
    
    public ListNode reverseBetween(ListNode head, int m, int n) {
        ListNode dummy = new ListNode(42);
        dummy.next = head;
        ListNode ptr1 = dummy;
        ListNode ptr2 = dummy;
        // finds the endpoint of the left segment
        for (int i = 0; i < m - 1; i++) {
            ptr2 = ptr2.next;
        }
        // finds the endpoint of the right segment
        for (int i = 0; i < n + 1; i++) {
            ptr1 = ptr1.next;
        }
        // finds the tail of the reversed linked list
        ListNode t = ptr2.next;
        // reverses a part of the linked list and gets its head
        ListNode h = reverseN(t, n - m + 1);
        // links up the left segment with the head of the reversed linked list
        ptr2.next = h;
        // links up the right segment with the tail of the reversed linked list
        t.next = ptr1;
        
        return dummy.next;
    }
}