在链表的末尾插入使用递归与迭代

Question

使用递归在链表末尾插入的函数如下所示

     // 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);
     }

但是如果我做同样的迭代，它不会以同样的方式工作，它只生成一个节点。

     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.
   }

我有严重的精神阻塞。谁能告诉我为什么不行?我该怎么做才能使它工作呢?

Answer 1

这里的问题是，您循环直到go不为空。一旦固定，循环直到go为空，

那么您只需用new覆盖空指针。但这不会链接到你现有的列表。

这样做:

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.
}

在第一次迭代时，go保证为非空(通过第一个if条件检查)。只需检查第一个next元素为null，并在这里插入新节点。