两个共享同一个节点和析构函数的单链表，两次删除同一个内存

Question

链表1: 3->6->9->15->30

链表2: 10->15->30

链表1和2在15处相交，并且共享相同的节点15和30。

我有两个链表，我正在搜索相交的节点，它是15。在程序结束之前，链表析构函数被调用。第一次析构函数调用释放了内存，没有任何问题。然后第二个列表尝试删除它自己的节点15。析构函数试图删除已经释放的内存，这会导致程序崩溃。我该如何解决这个问题？

Answer 1

首先，让我指出，您的列表通常不应该包含相同的节点。如果您需要列表之间的共享对象，请将指向对象的指针或引用保存在节点中，而不是共享节点本身。

如果你必须共享节点本身，你需要的是reference counting。

本质上，您要做的是跟踪指向特定对象的指针或引用的数量(在变量中)，并仅在该数量变为0时才释放内存，这表明该对象不再可访问，应该被释放。

要对STL进行引用计数，可以使用shared_ptr，它从C++11开始就在STL中。

struct node
{
    node(const data_t&);
    data_t data;
    std::shared_ptr<node> next;
};

auto head1 = std::make_shared(some_data1);
auto head2 = std::make_shared(some_data2);
head1->next = std::make_shared(some_data);
head2->next = head1->next;
//note that you do NOT copy the raw pointer, you must copy the shared_ptr itself

head1.reset();  //destroys some_data1 but not some_data
head2.reset();  //destroys some_data2 and some_data