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.
Example 1:
Input:
{"$id":"1","next":{"$id":"2","next":null,"random":{"$ref":"2"},"val":2},"random":{"$ref":"2"},"val":1}
Explanation:
Node 1's value is 1, both of its next and random pointer points to Node 2.
Node 2's value is 2, its next pointer points to null and its random pointer points to itself.
Note:
You must return the copy of the given head as a reference to the cloned list.
My code:
"""
# Definition for a Node.
class Node(object):
def __init__(self, val, next, random):
self.val = val
self.next = next
self.random = random
"""
class Solution(object):
def copyRandomList(self, head):
"""
:type head: Node
:rtype: Node
"""
if head==None:
return head
record_dict={}#Map one head to other head
now=head.next
pre_copy=Node(head.val,None,None)
head_now=pre_copy
record_dict[head]=head_now
while now:
now_copy=Node(now.val,None,None)
record_dict[now]=now_copy
pre_copy.next=now_copy
now=now.next
pre_copy=now_copy
now=head
now_copy=head_now
while now:
if now.random!=None:
point_node=record_dict[now.random]
now_copy.random=point_node
now=now.next
now_copy=now_copy.next
return head_now
Solution： https://leetcode.com/problems/copy-list-with-random-pointer/