这种复制链表的方法是正确的吗？

void InsertAtTail(struct node** headref,int val) 
{ 
    struct node *current,*newnode; 
    current=*headref; 
    newnode=malloc(sizeof(struct node)); 

    if(current==NULL) 
    { 
     newnode->data=val; 
     newnode->next=NULL; 
     *headref=newnode; 
     current=*headref; 
    } 

    else 
    { 

     while(current->next!=NULL) 
     { 
      current=current->next; 
     } 

     newnode->data=val; 
     newnode->next=NULL; 
     current->next=newnode; 
    } 
} 

struct node* CopyList(struct node* headref) 
{ 
    struct node* newlist=NULL; 
    struct node* current; 
    current=headref; 


    if(current==NULL) 
    { 
     newlist=current; 
    } 

    else 
    { 
     while(current!=NULL) 
     { 
      InsertAtTail(&newlist, current->data); 
      current=current->next; 
     } 

    } 
    return (newlist); 
}

我正在浏览斯坦福的CS101笔记，并找到了制作链表副本的代码。但它也使用了指向尾节点的指针。我已经编写了这个代码而不使用那个（尾指针）。我是链接列表的新手。请告诉我，我是否也可以这样做。当我印刷原件和复印件的地址时，两者都不同。我在Xcode中使用c。这种复制链表的方法是正确的吗？

来源

2013-08-22 Kunal Shrivastava

你试过看看它是否有效？ –

是的代码工作正常。正如我所提到的，当我打印检查两个链接列表的节点（原始和副本）的地址时，会为两个链接列表的相应节点显示不同的地址。 –

好吧，不使用尾指针会让你的列表非常慢 - 列表副本是O（n^2），所以即使主要是自以为是的答案，我会说你的代码是错误的。 –

作品不正，虽短：

void InsertAtTail(struct node** ref,int val) 
{ 
    while (*ref != NULL) { 
     ref = &(*ref)->next; 
    } 
    struct node *newnode = malloc(sizeof(struct node)); 
    newnode->data=val; 
    newnode->next=NULL; 
    *ref = newnode; 
}

而且列表复制应该改写：N²/ 2。

来源

2013-08-22 07:07:15

这种复制链表的方法是正确的吗？

回答

相关问题