My C++ solution using a pointer to pointer


  • 0
    S
    class Solution {
    public:
        ListNode *reverseBetween(ListNode *head, int m, int n) {
            ListNode** rstart=&head;
            int i=1;
            
            // Loop invariant
            // 1. *rstart always point to the first node of the reverse part
            // 2. rend always point to the last node of the reverse part
            // 3. head always point to the first node of the final list
            for(ListNode *rend=0, *nextNode=head;i<=n;i++){
                if(i==m){
                    rend=nextNode;
                    *rstart=nextNode;
                    nextNode=rend->next;
                }
                else if(i>m){
                    rend->next=nextNode->next;
                    nextNode->next=*rstart;
                    *rstart=nextNode;
                    nextNode=rend->next;
                }else{
                    rstart=&((*rstart)->next);
                    nextNode=nextNode->next;
                }
            }
            
            return head;
        }
    };

Log in to reply
 

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