LeetCode[138] Copy List with Random Pointer

novo 发布于2019-08-14 15:57 / 1531人阅读

LeetCode[138] Copy List with Random Pointer

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list

Map

复杂度
O(N), O(N)

思路
和clone graph一样的思路。先copy顺序的，再copy那些random的pointer.

代码

public RandomListNode copyRandomList(RandomListNode node) {
    Map map = new HashMap<>();
    RandomListNode dummy = new RandomListNode(0);
    RandomListNode p = head, q = head;
    // used to connect the new list;
    RandomListNode phead = dummy;
    while(p != null) {
        RandomListNode cp = new RandomListNode(p.label);
        map.put(p, cp);
        p = p.next;
        phead.next = cp;
        phead = phead.next;
    }
    while(q != null) {
        map.get(q).random = map.get(q.random);
        q = q.next;
    }
    return dummy.next;
}

GPU云服务器云服务器 Pointer LeetCode 138vps ddd138

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/66136.html

leetcode138. Copy List with Random Pointer

摘要：题目要求假设存在这样一个链表，在链表的每一个节点中，除了记录了自身值和指向下一个节点的指针，还有一个随机指针指向链表中任意一个节点。所以可以在两次遍历后完成任务。最后一圈遍历，我们调整指针，恢复原链表和塑造新链表。题目要求 A linked list is given such that each node contains an additional random pointer ...

Kross 2019-08-16 10:47 评论0 收藏0
LeetCode 138：复制带随机指针的链表 Copy List with Random Poin

摘要：给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。要求返回这个链表的深拷贝。提示你必须返回给定头的拷贝作为对克隆列表的引用。确定随机节点的关系之后再拆分链表。其时间复杂度为，空间复杂度为。给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。要求返回这个链表的深拷贝。 A linked list is g...

entner 2019-08-19 10:13 评论0 收藏0
LeetCode 138：复制带随机指针的链表 Copy List with Random Poin

摘要：给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。要求返回这个链表的深拷贝。提示你必须返回给定头的拷贝作为对克隆列表的引用。确定随机节点的关系之后再拆分链表。其时间复杂度为，空间复杂度为。给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。要求返回这个链表的深拷贝。 A linked list is g...

Lucky_Boy 2019-07-31 11:31 评论0 收藏0
[Leetcode] Copy List with Random Pointer 复制随机指针

摘要：栈迭代复杂度时间空间如果不算新链表的空间则是思路由于随机指针有可能产生环路，我们不能直接沿着随机指针的方向一个一个复制。同时我们又不能沿着指针直接复制，因为我们不知道随机指针所指向的新节点是哪个。 Copy List with Random Pointer A linked list is given such that each node contains an additiona...

Olivia 2019-08-14 12:25 评论0 收藏0
[LintCode/LeetCode] Copy List with Random Pointer

摘要：大体意思就是，先复制到，顺便将所有的放在再复制所有的到，顺便将所有的放在最后令，令，将和分离，返回的头结点 Problem A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null. ...

Jacendfeng 2019-08-14 15:32 评论0 收藏0