在第二個位置插入列表C++

Question

我想在列表中插入一個元素作爲第二個元素，創建一個新列表而不修改原來的列表。

實施例： 列表1 2 3 4 5，CIN >> 55，然後新的列表成爲1 55 2 3 4 5

問題是，這兩個列表進行修改。這是爲什麼發生？

ptr_list insertAfterFirstElem(ptr_list head){ 
    ptr_list tmp; 
    tmp=new list; 
    cout<<"Insert value"<<endl; 
    cin>>tmp->val; 
    tmp->next=head->next; 
    head->next=tmp; 
    return (head); 

} 

我寫了一個insertAtTop功能工作正常：

ptr_list insertAtTop(ptr_list head){ 
    ptr_list tmp; 
    tmp=head; 
    head=new list; 
    cout<<"Insert value"<<endl; 
    cin>>head->val; 
    head->next=tmp; 
    return (head); 

} 

你能解釋一下什麼是這兩個函數之間的區別？爲什麼insertAtTop（）不會修改原始列表？

Answer 1

這兩個列表共享相同的單元格;這就是爲什麼你有麻煩。

head: xxx -> yyy -> zzz -> ttt 
    ^
res: --| 

如果tmp = UUU，你是在第二位置插入它，

head: xxx -> uuu-> yyy -> zzz -> ttt 
    ^ ^
res: --|  |-- tmp 

但是，正如你所看到的，從開始head原始列表也被修改。

如果你不想修改它，你需要在插入之前複製原始列表：

head: xxx -> yyy -> zzz -> ttt 
copy: xxx -> yyy -> zzz -> ttt 
    ^
res: --| 

，那麼你可以插入

head: xxx -> yyy -> zzz -> ttt 
copy: xxx -> uuu-> yyy -> zzz -> ttt 
    ^ ^
res: --|  |-- tmp 

一個可能的解決辦法是：

ptr_list copyList(ptr_list head) { 
    ptr_list copy = nullptr; 
    ptr_list* copy_last = © 
    for (ptr_list iter = head; iter != nullptr; iter = iter->next) { 
     *copy_last = new list(*iter); 
     copy_last->val = iter->val; 
     copy_last->next = nullptr; 
     copy_last = &copy_last->next; 
    }; 
    return copy; 
} 

ptr_list insertAfterFirstElem(ptr_list head){ 
    ptr_list copy = copyList(head); 
    ptr_list tmp; 
    tmp=new list; 
    cout<<"Insert value"<<endl; 
    cin>>tmp->val; 
    tmp->next=copy->next; 
    copy->next=tmp; 
    return (copy); 
} 

現在與insertAtTop(ptr_list head)你仍然有分享的問題，但你不要沒有立即看到它。它創建

head: xxx -> yyy -> zzz -> ttt 
     ^
res: uuu --| 

所以，如果一段時間後，你想從head插入第二位置的另一小區也將修改你的結果。

的執行，而無須任何insertAtTop股的

ptr_list insertAtTop(ptr_list head){ 
    head = copyList(head); 
    ptr_list tmp; 
    ... 
} 

也不要忘記釋放細胞。如果您不使用像reference-counting這樣的其他機制，則免費使用股票幾乎是不可能的。