LC 92 Reverse Linked List II

We will iterate to the node before the start of the reversion. Then reverse.At the time of reverse, curr -> next will point to the tail of reversed inner linked list.
After reverse, we have three linked list, the first part, the reversed part, and the third part.
We want to point the tail of first part to the head of reversed part, which is pointed by prev. We also need to point the tail of reversed part, which is pointed by curr -> next, to head of third part, which is pointed by tempCurr.

tempCurr will point to the node after reversed inner linked list.

/**
 * 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;
        //go ahead m - 1 step and reverse (n - m + 1 times )
        //then point prev 
        ListNode dummyNode(-1);
        dummyNode.next = head;
        ListNode* curr = &dummyNode;
        for(int i = 0; i < m - 1; i ++){
            curr = curr -> next;
        }
        //curr will be right before the to-be-reversed node


        ListNode* tempNext = NULL;
        ListNode* prev = NULL;
        ListNode* tempCurr = curr -> next;
        for(int i = m - 1; i < n; i ++){
            tempNext = tempCurr -> next;
            tempCurr -> next = prev;
            prev = tempCurr;
            tempCurr = tempNext;
        }
        //after reversing n - m + 1 nodes, prev will be on the next node
        //need to point tail of reverse(pointed by curr -> next) to tempCurr.
        //need to point curr to head of reversed(pointed by prev) to tempCurr
        curr -> next -> next = tempCurr;
        curr -> next = prev;

        return dummyNode.next;
    }
};

Leave a Reply

Your email address will not be published. Required fields are marked *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax