Reverse Linked List II

题目
Reverse a linked list from position m to n. Do it in one-pass.

Note: 1 ≤ m ≤ n ≤ length of list.

Example:

Input: 1->2->3->4->5->NULL, m = 2, n = 4
Output: 1->4->3->2->5->NULL

答案

class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if(head == null) return null;

        // Define a dummy node to simplify code
        ListNode dummy = new ListNode(0);
        dummy.next = head;

        // First step: find node m and its previous node
        ListNode curr_node = head, prev_node = dummy;
        int curr;
        for(curr = 1; curr < m; curr++) {
            prev_node = curr_node;
            curr_node = curr_node.next;
        }
        ListNode m_node = curr_node, m_prev_node = prev_node;

        // Iterate from node m to node n, reversing stuff along the way
        for(; curr <= n; curr++) {
            ListNode next = curr_node.next;

            curr_node.next = prev_node;
            prev_node = curr_node;

            curr_node = next;
        }
        // In the end, point m_prev_node to n_node, point m_node to the node after n_node
        m_prev_node.next = prev_node;
        m_node.next = curr_node;
        
        // head is dummy's next
        return dummy.next;
    }
}