带有随机指针的链表的深层副本

Question

这是一个leetcode面试问题，要求提供链表的深层副本，该链表具有一个random成员，该成员可以指向任何元素。 （https://leetcode.com/problems/copy-list-with-random-pointer）。我不知道为什么我的解决方案会因访问错误而给出运行时错误。

这是我的解决方法：

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;

    Node() {}

    Node(int _val, Node* _next, Node* _random) {
        val = _val;
        next = _next;
        random = _random;
    }
};
*/
class Solution {
public:
    Node* copyRandomList(Node* head) {
        unordered_map<Node*, Node*> node_map;
        Node* copy_head = new Node();

        Node* node = head;
        Node* copy = copy_head;

        while (node) {
            node_map[node] = copy;
            copy->val = node->val;
            if (node->next)
                copy->next = new Node();
            node = node->next;
            copy = copy->next;
        }

        node = head;
        copy = copy_head;

        while (node) {
            copy->random = node_map[node->random];
            node = node->next;
            copy = copy->next;
        }

        return copy_head;        
    }
};

Answer 1

问题是您的副本没有以空指针终止。也就是说，其最后一个节点不在其nullptr成员变量中存储next。

您通过new node()创建副本的节点，该调用调用默认的构造函数。但是，此默认构造函数不执行任何操作，包括不初始化成员变量。因此，您需要将最后一个节点的next手动设置为nullptr。