在第二个位置插入列表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这样的其他机制，则免费使用股票几乎是不可能的。