George MIT George MIT - 1 month ago 8
C++ Question

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 ?

Answer

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.