https://leetcode.cn/problems/copy-list-with-random-pointer/
问题分析https://www.algomooc.com/708.html
代码实现 java
class Solution {
public Node copyRandomList(Node head) {
if(head==null)return null;
Node cur=head;
Map map=new HashMap<>();//哈希map用来存储已经创建的节点
//第一次遍历
while(cur!=null)
{
map.put(cur,new Node(cur.val));
cur=cur.next;
}
//第二次遍历
cur=head;
while(cur!=null)
{
Node valcur=map.get(cur);
Node valNextNode=map.get(cur.next);
valcur.next=valNextNode;
Node valRandomNode=map.get(cur.random);
valcur.random=valRandomNode;
cur=cur.next;
}
return map.get(head);
}
}
c++
class Solution {
public:
Node* copyRandomList(Node* head) {
if(head==NULL)return NULL;
Node* cur=head;
unordered_map map;
while(cur!=NULL)
{
Node *valNode=new Node(cur->val);
map[cur]=valNode;
cur=cur->next;
}
cur=head;
while(cur!=NULL)
{
Node* valcur=map[cur];
Node* valNextNode=map[cur->next];
valcur->next=valNextNode;
Node* valRandomNode=map[cur->random];
valcur->random=valRandomNode;
cur=cur->next;
}
return map[head];
}
};
python
"""
# Definition for a Node.
class Node:
def __init__(self, x, next=None, random=None):
self.val = int(x)
self.next = next
self.random = random
"""
class Solution(object):
def copyRandomList(self, head):
"""
:type head: Node
:rtype: Node
"""
if head == None :
return None
cur=head
map=dict()
while cur!=None:
new_node=Node(cur.val,None,None)
map[cur]=new_node
cur=cur.next
cur=head
while cur!=None:
valcur=map.get(cur)
valNextNode=map.get(cur.next)
valcur.next=valNextNode
valRandomNode=map.get(cur.random)
valcur.random=valRandomNode
cur=cur.next
return map.get(head)
