LeetCode 138. Copy List with Random Pointer

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

LeetCode 138. Copy List with Random Pointer 原题链接中等

作者：

yxc , 2018-05-31 17:07:11 , 所有人可见 , 阅读 3362

7

5

题目描述

给定一个单链表，链表中的每个节点包含一个额外的指针，随机指向链表中的其它节点或者指向 null。
请复制整个链表，并返回新链表的头结点。

算法

(哈希表) $O(n)$

用哈希表维护新旧链表节点之间的对应关系。

从前往后扫描旧链表，对于每个节点的两条边（*next以及*random），如果新链表中对应的点还未创建，则创建节点，并将新节点与旧链表中的节点关联起来，然后根据节点之间的映射关系，在新链表中添加这两条边（*next以及*random）。

时间复杂度分析：整个链表仅被扫描一遍，所以时间复杂度是 $O(n)$。

C++ 代码

/*
// 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 0;
        unordered_map<Node*, Node*> hash;
        Node *root = new Node(head->val, NULL, NULL);
        hash[head] = root;
        while (head->next)
        {
            if (hash.count(head->next) == 0)
                hash[head->next] = new Node(head->next->val, NULL, NULL);
            hash[head]->next = hash[head->next];

            if (head->random && hash.count(head->random) == 0)
                hash[head->random] = new Node(head->random->val, NULL, NULL);
            hash[head]->random = hash[head->random];

            head = head->next;
        }

        if (head->random && hash.count(head->random) == 0)
            hash[head->random] = new Node(head->random->val, NULL, NULL);
        hash[head]->random = hash[head->random];

        return root;
    }
};

13 评论

一碗好心情 1个月前

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(!head) return 0;
        unordered_map<Node*, Node*> hash;
        Node* root = new Node(head->val);
        hash[head] = root;
        hash[NULL] = NULL;
        while(head){

            if(!hash.count(head->next)) hash[head->next] = new Node(head->next->val);
            hash[head]->next = hash[head->next];    

            if(head->random && !hash.count(head->random)) hash[head->random] = new Node(head->random->val);
            hash[head]->random = hash[head->random];
            head = head->next;
        }
        return root;
    }
};

Omega_ 2020-03-29 14:10

我给下面那个方法起了个名字叫二分裂= =

yxc 2020-04-04 04:36

233333

greg666 2019-04-13 00:19

突然看不到生命的颜色，使我感到不安。

greg666 2019-04-13 00:16

只是简单替换，RandomListNode->Node, label->val。我自己原来的代码也通过不了了。大佬的代码也通过不了了。可能是leetcode本身的问题。请大佬看一眼。

yxc 2019-04-14 01:43

代码已修正

greg666 2019-04-14 07:36 回复了 yxc 的评论

原来leetcode不光换了变量的名字，constructor也改了。谢佬。

greg666 2019-04-13 00:14

leetcode坑爹啊。把RandomListNode换成Node了。结果yxc的代码通过不了了。

    Node *copyRandomList(Node *head) {
        if (!head) return 0;
        unordered_map<Node*, Node*> hash;
        Node *root = new Node(head->val);
        hash[head] = root;
        while (head->next)
        {
            if (hash.count(head->next) == 0)
                hash[head->next] = new Node(head->next->val);
            hash[head]->next = hash[head->next];

            if (head->random && hash.count(head->random) == 0)
                hash[head->random] = new Node(head->random->val);
            hash[head]->random = hash[head->random];

            head = head->next;
        }

        if (head->random && hash.count(head->random) == 0)
            hash[head->random] = new Node(head->random->val);
        hash[head]->random = hash[head->random];

        return root;
    }

威 2019-02-19 13:07

idea 大概是这样的：
1. Iterate the original list and duplicate each node. The duplicate
of each node follows its original immediately.
2. Iterate the new list and assign the random pointer for each
duplicated node.
3 . Restore the original list and extract the duplicated nodes.

yxc 2019-02-20 16:27

这个解法很赞！可以把额外的空间复杂度从 $O(n)$ 优化到 $O(1)$。

greg666 2019-04-14 07:41 回复了 yxc 的评论

我背诵的方法就是这个。

Node* copyRandomList(Node* head) {
    if (!head) {
        return NULL;
    }

    Node* cur = head;
    while (cur) {
        Node* copy = new Node(cur->val, cur->next, NULL);
        cur->next = copy;
        cur = copy->next;
    }

    cur = head;
    while (cur) {
        if (cur->random) {
            cur->next->random = cur->random->next;
        }
        cur = cur->next->next;
    }

    cur = head;
    Node* copied = cur->next;
    while (cur) {
        Node* temp = cur->next;
        cur->next = temp->next;
        if (cur->next) {
            temp->next = cur->next->next;
        }

        cur = cur->next;
    }

    return copied;  
}

威 2019-02-19 12:59

看到了一个O（1）的解法我觉得挺有意思的 https://www.youtube.com/watch?time_continue=911&v=OvpKeraoxW0

gyh 2019-05-01 19:29

good!

App 内打开