My c++ AC code.


  • 0
    inline ListNode* reverseBetween(ListNode* head, int m, int n) {
        if(!head || !(head->next) || m==n) return head;
        
        int i;
        //the following node represents respectively to:
        // move-pointer  dummy-node             a[m-1]        head-of-reversed-part  a[m]   a[m+2]
        ListNode *p=0, *fkNode=new ListNode(0), *am_minus_1=0, *revPartHead=0,       *am=0, *am_plus_2=0;
        fkNode->next=head;
        if(m==1) am_minus_1=fkNode;
    
        //Traverse the list only one time.
        for( i=1,p=head; p; ++i){
            if(i>m && i<=n){
                //Save next node.
                am_plus_2=p->next;
                //Insert
                am_minus_1->next=p;
                p->next=revPartHead;
                revPartHead=am_minus_1->next;
                am->next=am_plus_2;
                p=am_plus_2;
            }else{
                if(i>n){
                    am->next=p;
                    am=p;
                }else if(i==m){
                    revPartHead=p;
                    am=p;   
                }else if(i==m-1){
                    am_minus_1=p;
                }
                p=p->next;
            }
        }
    
        if(m==1) return fkNode->next;
        return head;
    }
    

Log in to reply
 

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