时间戳

首页 > 解决方案 > 带有随机指针的链表的深拷贝

c++ - 带有随机指针的链表的深拷贝

问题描述

这是一个 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;        
    }
};

标签： c++pointerslinked-list

解决方案

您的第一个while循环不是分配链表新副本的首选或规范方式。应该只有 1 次调用new，在循环内，而不是在循环外。如果head为空，您仍在分配一个Node您不应该分配的值。

更重要的是，您Node的复制代码使用的默认构造函数不会初始化任何数据成员，尤其是next指针。因此，您最后复制的节点将具有一个可能不为空的随机不确定值，因此它不会正确地以空值终止列表。

尝试更多类似的东西：

/*
// 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) {
        if (!head)
            return nullptr;

        unordered_map<Node*, Node*> node_map;
        Node* copy_head = nullptr;
        Node** copy = &copy_head;
        Node* node = head;

        do {
            *copy = new Node(node->val, nullptr, nullptr);
            node_map.insert(make_pair(node, *copy));
            copy = &((*copy)->next);
            node = node->next;
        }
        while (node);

        node = copy_head;

        do {
            if (head->random)
                node->random = node_map[head->random];
            node = node->next;
            head = head->next;
        }
        while (head);

        return copy_head;
    }
};

推荐阅读