c++ - 如何深拷贝链表对象指针

Question

我正在尝试创建一个函数，该函数将在给定指向整数数组的指针的情况下创建一个新的链表。

这是我的代码，下面是更多信息:

#include "iostream"


using namespace std;

//Definition for singly-linked list.
struct ListNode {

    //members
    int val;
    ListNode *next;

    //constructor
    ListNode(int x) : val(x), next(NULL) {}

    //overload assignment operator
    void operator=(const ListNode &right_list ) { 
        val = right_list.val;
        next = right_list.next;
    }   

};

//error here:
//creating new linked list
ListNode*  createNewList(int* x, int length) {
    if (*x == NULL) return NULL;
    ListNode newList = ListNode(-1);
    ListNode* ptr = &newList;
    int count = 0;
    while (count < length) {
        ptr->val = *(x + counter);
        ListNode newElement = ListNode(-1);
        ptr->next = &newElement;
        ptr = ptr->next;
        counter++;
    }
    ListNode* returnPtr = &newList;
    return returnPtr;
}

int main() {


    //create List contents
    int x [5] = {2, 4, 5, 7, 9};
    int* y = x;

    //create list: doesn't work.
    ListNode* newList = createNewList(y, 5);

    cout << "debug test: neList first val is " << newList->val << endl;

    return 0;
}

使用gdb我发现错误在线:

ptr->next = &newElement;

在 while 循环之后列表有元素 {2, -1, -1, -1, -1}。我相信这是因为我只是将 ptr->next 设置到 newElement 的地址，而不是创建一个与 newElement 相同的 ListNode 的新实例并在其旁边设置 ptr->next。

但我认为要避免这种情况，并确保“=”符号产生深拷贝，我只需要重载 ListNode 类中的赋值运算符，我就这样做了。

此外，在 createNewList fn 结束之前的 returnPtr->val 的值是 2(我用 gdb 验证了这一点)，但是 cout 语句每次打印不同的值，所以它是某种形式的未定义行为。我不明白原因。

如果我研究并发现任何新的东西，我会分享。我也可以根据要求提供更多信息。我真的很想了解指针移动语义，因此链接到其他可能适用的情况或文章将大有帮助:)

感谢阅读 :) 任何信息都将不胜感激!

Answer 1

您正在堆栈上创建列表元素，因此一旦您离开函数它们就会消失。

代替

ListNode newElement = ListNode(-1);

尝试

ListNode* newElement = new ListNode(-1);

例如

ListNode*  createNewList(int* x, int length) {
    if (x == nullptr) return x;
    ListNode* newList = new ListNode(-1);
    ListNode* ptr = newList;
    int count = 0;
    while (count < length) {
        ptr->val = *(x + counter);
        ListNode* newElement = new ListNode(-1);
        ptr->next = newElement;
        ptr = ptr->next;
        counter++;
    }
    return newList;
}

这里没有必要

int x [5] = {2, 4, 5, 7, 9};
int* y = x;

//create list: doesn't work.
ListNode* newList = createNewList(y, 5);

您可以改为直接传递 x

ListNode* newList = createNewList(x, sizeof(x)/sizeof(*x));