在链表中插入一个链表

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

您的代码存在一些问题。

一个问题是，它不清楚你期望从插入函数。

其他要插入的列表在哪里？我会假设该索引应该意味着otherList的头部将成为位置索引处的节点（从零开始计数）。这也是你的代码是做指数= 0，但对于指数= 1你居然后插入当前元素数1。这可以是固定的改变，同时，即

while (x > 1) 

另一个问题是，在使用指针之前您不检查nullptr。这一定是固定的。

第三个问题是，你当指数> 0

我不知道，如果你的拷贝构造函数是确定你没有提供的代码没有得到一个副本。

这里是另一种方法（镶嵌功能改名为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 ::载体，而不是创建自己的列表中。