Reverse Linked List II

Reverse Linked List IIJun 27 '12

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.

This looks fairly easy but actually it's pretty tricky. Each recursion takes the node to be processed and returns itself so that the upper level can change the 'next' pointer backwards as stack pops. The special case is that during the backward process, when m == 0 we reach the first node in the region to be reversed (let's call it 'region'). At that time the node before it should get the next node after the 'region'. That's where the nodeAfterN is used. Also the node before m == 0 should get the original last node in the 'region', which now becomes the head node in the 'region'. This is achieved by returning the pointer of that last node to the upper level of recursion, AKA nodeAtN.

/**
 * 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) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        nodeAtN = NULL;
        nodeAfterN = NULL;
        return revHelper(head, m - 1, n - 1);
    }
    
    ListNode *revHelper(ListNode *current, int m, int n) {
        if (!current) return NULL;
        ListNode *ret = current;
        if (m > 0) {
            current->next = revHelper(current->next, m - 1, n - 1);
        }
        else if (n > 0) {
            ListNode *currentNext = revHelper(current->next, m - 1, n - 1);            
            currentNext->next = current;
            if (m == 0) {
                current->next = nodeAfterN;
                ret = nodeAtN;
            }
        }
        else if (n == 0) {
            nodeAtN = current;
            nodeAfterN = current->next;
        }
        return ret;
    }
    
private:
    ListNode *nodeAfterN;
    ListNode *nodeAtN;
};