Reverse Link List II

• Time : $O()$
• Space : $O()$

c++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
ListNode* nThNode(ListNode* A, int n) {
    ListNode* runner = A;
    while(n--) runner = runner->next;
    return runner;
}
ListNode* reverse(ListNode* A) {
    ListNode* dummy = new ListNode(-1);
    while(A) {
        ListNode* nxt = A->next;
        A->next = dummy->next;
        dummy->next = A;
        A = nxt;
        
    }
    
    return dummy->next;
}
ListNode* Solution::reverseBetween(ListNode* A, int B, int C) {
    if(B == C) return A;
    ListNode* dummy = new ListNode(-1);
    dummy->next = A;
    ListNode *lb = nThNode(dummy, B-1), *right = nThNode(dummy, C);
    ListNode *left = lb->next, *rb = right->next;
    lb->next = right->next = NULL;
    lb->next = reverse(left);
    ListNode* runner = dummy;
    while(runner->next) runner = runner->next;
    runner->next = rb;
    
    return dummy->next;
}