Why my program wrong?


  • 0
    P
    class Solution {
    
       public:   
        ListNode* node;
        ListNode* reverseList(ListNode* head) {
              reverse_recursion( head , NULL );
        }
    
        ListNode* reverse_recursion(ListNode *head , ListNode* np){
            if(head == NULL) return node;
            else
            {
                
                // ListNode *tmp = head->next;
                node = head;
                node->next = np;
                // return node;
               
                reverse_recursion( head->next , head);
            }
        }
       };

  • 0
    L

    I believe your recursion is a bit incorrect. See the correct version below

    **Build topdown along the way **

    ListNode* reverseList_alongtheway(ListNode* head, ListNode* prev=NULL) {
    
    if(head == NULL)
        return prev;
    
    ListNode* rem =head->next;
    head->next=prev;        
    return reverseList(rem, head);
    }
    

    Recursive bottom up

        ListNode* reverseList(ListNode* head) {
    
        if(head ==NULL || head->next==NULL)
            return head;
        
        //Assume we get a reverse list for all nodes other than head
        // in *rem.
        ListNode* rem=reverseList(head->next);
        
        //now head should be added to the end of rem's list. 
        // the last node of rem's list is same as the head's next.
        // so point it to head.
        head->next->next=head;
        // point head to null to mark the end.
        head->next= NULL;
        
        return rem;
            
    }
    

    Iterative

    ListNode* reverseList_it(ListNode* head) {
        
        ListNode *rem;
        ListNode *prev=NULL;
        while(head)
        {
            rem=head->next;
            head->next =prev;
            prev=head;
            head=rem;
        }
        return prev;
    
    }
    

    };


Log in to reply
 

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