代码之家 › 专栏 › 技术社区 › Duxa

不确定我的递归链表删除函数为什么工作?希望得到解释

singly-linked-list pointers c++

Duxa · 技术社区 · 7 年前

我写了一个程序,它是有效的,但我认为它不应该。有人能解释一下为什么它有效吗?

我有一个单链表。这是一个项目,所以我不能张贴直接代码,但我会改变一点问题

假设我的链表是一个数字1,2,3,4,4,5的列表

我需要扫描列表并删除任何重复项,因此我需要删除其中一个4。我需要通过递归来完成。

我正在编写的函数有它的参数/参数作为指向列表开头的指针,我将调用它指针

//Base cases up here
if (pointer->value == pointer->next->value){
    *toDelete = pointer;
     pointer = pointer->next;
     delete toDelete;
     recur the function
} else recur(pointer->next);

现在这段代码可以工作了,我不认为应该这样做,因为我从未将前一个节点连接到我删除的节点之后的节点。然而,当我看到结果时,所有适当的节点都连接起来了,所有应该被删除的节点都被删除了。我是不是误解了什么?做 指针=指针->下一个 不仅仅是点指针到下一个节点的地址?

谢谢

1 回复 | 直到 7 年前

R Sahu 7 年前

现在这段代码可以工作了,我不认为应该这样做,因为我从未将前一个节点连接到我删除的节点之后的节点。

这是正确的。您的函数可能看起来有效,但它确实显示出未定义行为的迹象。您需要使用:

if ( pointer->next != nullptr && pointer->value == pointer->next->value){
    auto toDelete = pointer->next;
    pointer->next = pointer->next->next;
    delete toDelete;

    // Recurse with the same pointer since you might have 4 4 4
    // in the original list.
    recur(pointer);
}
else {    
   recur(pointer->next);
}

推荐文章

Walter · 添加到列表功能

7 年前

apm · Java中的数据结构,带有删除节点后所有节点的操作

7 年前