插入链表到链表

Question

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

有什么方法可以在现有链表（中间）中插入另一个链表而不引起这个问题？

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 copy\n" << (*this) << endl;
}

Answer 1

您的代码存在一些问题。

一个问题是不清楚您对插入函数的期望。

要插入的另一个列表在哪里？我会假设 index 应该意味着 otherList 的头部将成为位置索引处的节点（从零开始计数）。这也是您的代码为 index=0 所做的，但对于 index=1 您实际上在 之后插入 当前元素编号 1。这可以通过更改 while 来解决，即

while (x > 1)

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

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

我不确定你的copy ctor是否正常，因为你没有提供代码。

这是另一种方法（插入函数重命名为 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;
    }
}

顺便说一句 - 考虑使用 std::vector 而不是创建自己的列表。

插入链表到链表

Insert a linked list to a linked list

c++

algorithm

memory-management

linked-list

data-structures