将链表插入到链表中

Question

我编写了这个函数，它将另一个链表插入到现有的链表中。当我打印出函数中"this"对象的值时，输出是正确的。但是，当最后调用析构函数时，程序会遇到运行时错误。我认为运行时错误是由两个指针指向同一地址引起的;因此，当一个被取消分配时，另一个就变成了悬空指针。

是否有任何方法可以将另一个链表插入到现有的链表(在中间)而不会引起此问题?

void List::insert(const List& otherList, const int &index)
{
    Node* insertion = head;
    int x = index;
    while (x > 0){
        insertion = insertion->next;
        x--;
    }
    if (index == 0){  //this works fine
        otherList.tail->next = insertion;
        *this = otherList;  /*I implemented a copy ctor 
                              that performs deep copy 
                              so this is also fine */
    }
    else{ // this block causes problems
        Node* tmp = insertion->next;
        insertion->next = otherList.head;
        otherList.tail->next = tmp;
    }
    cout << "after the copyn" << (*this) << endl;
}

Answer 1

你的代码有一些问题。

一个问题是您不清楚期望从插入函数中得到什么。

另一个要插入的列表在哪里?我认为index应该意味着otherList的头部将成为位置index处的Node(从0开始计数)。这也是您的代码为index=0所做的，但对于index=1，您实际上在后插入当前元素号1。这可以通过更改while来修复，例如

while (x > 1)

另一个问题是在使用指针之前没有检查nullptr。这个问题必须解决

第三个问题是当index> 0时没有得到副本。

我不确定你的复制器是否可以，因为你没有提供代码。

下面是另一种方法(insert-function重命名为insert_list_copy_at):

class Node
{
public:
    Node() : next(nullptr) {};
    Node(const Node& other)
    {
        next = other.next;
        // Copy other members
    };
    Node* next;
    // other members
};
class List
{
public:
    Node* head;
    Node* tail;
    void insert_list_copy_at(const List& otherList, int index);
    void insert_node_at(Node* node, int index);
};
void List::insert_node_at(Node* node, int index)
{
    if (index == 0)
    {
        node->next = head;
        head=node;
        if (tail == nullptr)
        {
            tail=node;
        }
            return;
    }
    if (head == nullptr) {/*throw exception - index out of range*/};
    Node* t = head;
    while(index>1)
    {
        t = t->next;
        if (t == nullptr) {/*throw exception - index out of range*/};
    }
    // Insert node after t
    node->next = t->next;
    t->next = node;
    if (tail == t)
    {
        tail=node;
    }
}
void List::insert_list_copy_at(const List& otherList, int index)
{
    Node* t = otherList.head;
    while(t != nullptr)
    {
        // Create new node as copy of node in otherList
        Node* tmp = new Node(*t);
        // Insert in this list
        insert_node_at(tmp, index);
        // Increment index and pointer
        index++;
        t = t->next;
    }
}

BTW -考虑使用std::vector而不是创建你自己的列表