CODEWITHSUNDEEP
c++recursionlinked-list
George MIT
George MIT

Reputation: 3

Insertion at end of linked list using recursion vs Iteration

The function to insert at end of linked list using recursion looks something like this 

     // Main..
     for(int i=0;i<n;i++){
       cin>>x;
       insert(head,x);
     }

     void insert(struct node*&h,int x){
      if(h==NULL){
       h=new node(x);
       return;
      }
      insert(h->next,x);
     }

But if I am doing same with iteration it doesn't work the same way,Its making only one node.

     void insert(struct node* &h,int x){
             if(h==NULL){
             h=new node(x);
             return;
            }
        struct node* go=h;
        while(go){     //At (go==NULL) it should point to next of last node
         go=go->next;   // I know it should be go->next!=NULL condition.
       }
         go=new node(x);//Assigning next of last to new node.
   }

I am having serious mental blockage.Can anyone please help why it doesn't work ? What should I do to make it work ?

Upvotes: 0

Views: 1102

Answers (1)

Jean-Fran&#231;ois Fabre
Jean-Fran&#231;ois Fabre

Reputation: 140168

The problem here is that you loop until go is not null. Okay, once fixed, you loop until go is null,

Then you just overwrite a null pointer by a new. But that doesn't link it to your existing list.

Do that instead:

void insert(struct node* &h,int x)
{
   if(h==NULL)
   {
     h=new node(x);
     return;
   }
   struct node* go=h;

   // move until last element
   while(go->next)
   { 
      go=go->next; 
   }
   // create a node at the end
   go->next=new node(x);//Assigning next of last to new node.
}

At first iteration, go is guaranteed to be non-null (checked by first if condition). Just check for the first next element to be null, and insert your new node here.

Upvotes: 1

Related Questions