Reverse Linked List II

Given a rotated sorted array, recover it to sorted array in-place.

Example

[4, 5, 1, 2, 3] -> [1, 2, 3, 4, 5]

Challenge

In-place, O(1) extra space and O(n) time.

Clarification

What is rotated array:

    - For example, the orginal array is [1,2,3,4], The rotated array of it can be [1,2,3,4], [2,3,4,1], [3,4,1,2], [4,1,2,3]

class Solution {
public:
    /**
     * @param head: The head of linked list.
     * @param m: The start position need to reverse.
     * @param n: The end position need to reverse.
     * @return: The new head of partial reversed linked list.
     */
    ListNode *reverseBetween(ListNode *head, int m, int n) {
        ListNode dummy(0);
        dummy.next = head;
        int i = 1;
        
        ListNode *p = &dummy;
        
        while(i < m && p) {
            p = p->next; 
            i++;
        }
        
        head = p;
        ListNode *tail = p->next;
        
        while(i < n) {
            ListNode *next = tail->next;
            tail->next = next->next;
            next->next = head->next;
            head->next = next; 
            i++;
        }
    
        return dummy.next;    
    }
};