92 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.

Solution

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        if ( head == NULL ) return head;
        ListNode *dummy = new ListNode(0);
        dummy->next = head;
        ListNode *ptail = dummy;
        for ( int i = 1; i <= m-1; i++ ) ptail = ptail->next;
        ListNode *p1 = ptail->next, *phead = ptail->next;
        ListNode *p2 = p1->next, *p3;
        for ( int i = m; i <= n-1; i++ ) {
            p3 = p2->next;
            p2->next = p1;
            p1 = p2;
            p2 = p3;
        }
        phead->next = p2;
        ptail->next = p1;
        return dummy->next;
    }
};

Note
Pay special attention to the loop condition!
Tricks to determine the loop condition:

• use practical cases to simulate the code while running.
• count how many times of operations should be done.
  For example:
  given 1->2->3->4->5->NULL, m = 2 and n = 4. The second loop to reverse should be done twice, thus (i_end - i_start + 1 ) should be 2, i.e. ( n-1 - m + 1 ) == 2.