Easiest c++ recursive implementation


  • 0
    A
    class Solution {
    public:
        ListNode* reverse(struct ListNode *head,int n,int count,struct ListNode **ans)
        {
            if(count==n)  // when nth node is reached store the address of next of nth node in ans 
            {
                *ans=head->next;
                return head;
            }
            
            // this is simple recursive code to reverse a linked list
            
            struct ListNode *temp=reverse(head->next,n,count+1,ans);
            head->next->next=head;
            head->next=NULL;
            return temp;
        }
        ListNode* reverseBetween(ListNode* head, int m, int n) {
            
             if(m==n)
                return head;
            
             int count=1;
            struct ListNode *temp=NULL,*p=head;
            
            while(count<m)  // Reach the mth node from head . temp is the prev node of p
            {
                count++;
                temp=p;
                p=p->next;
            }
            struct ListNode *ans;
            
            if(temp)   // reverse portion between m & n . when m=1 : temp=NULL 
                temp->next=reverse(p,n,m,&ans);
            else        // for cases where m=1 i.e. head is changed
                head=reverse(p,n,m,&ans);
            
            p->next=ans;  // ans contain the address of next node of n .
            return head;
        }
    };

  • 0
    V

    Good one, thanks


Log in to reply
 

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