這種複製鏈表的方法是正確的嗎？

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

這種複製鏈表的方法是正確的嗎？

回答

相關問題