c++ - 使用递归与迭代在链表末尾插入

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 为 null，

然后你只需用一个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 元素是否为空，然后在此处插入新节点。