Easy to understand C++ solution


  • 0

    This is a partial reversal, we need to find the left interface (let it be leftI, (m-1)th node) to link the head of reversed list, and the tail of reversed list will link with the right interface(let it be rightI, (n+1)th node). This sounds all right, what if m = 1? There is nothing left to the head. A common way to do is to introduce a dummy head. So now there are four things to do:

    1. Find and record leftI
    2. Reverse sublist [m,n] -> [rhead, rtail]
    3. Find and record rightI
    4. Relink: leftI->next = rhead, rtail->next=rightI 
    5. Return dummy->next
    

    Code

    class Solution {
    public:
        ListNode* reverseBetween(ListNode* head, int m, int n) { 
            if(n == m) return head;
            
            ListNode* dummy = new ListNode(0);
            dummy->next = head;
            ListNode *leftI = dummy;
            for(; --m; --n) leftI = leftI->next; 
    
            ListNode *cur = leftI->next, *rtail = cur, *pre = nullptr;
            while(cur){
                ListNode* nxt = cur->next;
                cur->next = pre;
                pre = cur;
                cur = nxt;
                if(!--n) break;
            }
            rtail->next = cur;  
            leftI->next = pre;
    
            return dummy->next;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.