Leetcode 138. Copy List with Random Pointer

Seawolf

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.

The Linked List is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:

val: an integer representing Node.val
random_index: the index of the node (range from 0 to n-1) where random pointer points to, or null if it does not point to any node.


Example 1:



Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]

Example 2:



Input: head = [[1,1],[2,1]]
Output: [[1,1],[2,1]]

Example 3:



Input: head = [[3,null],[3,0],[3,null]]
Output: [[3,null],[3,0],[3,null]]
Example 4:

Input: head = []
Output: []
Explanation: Given linked list is empty (null pointer), so return null.


Constraints:

-10000 <= Node.val <= 10000
Node.random is null or pointing to a node in the linked list.
Number of Nodes will not exceed 1000.

1. """
   
2. # Definition for a Node.
   
3. class Node:
   
4.     def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
   
5.         self.val = int(x)
   
6.         self.next = next
   
7.         self.random = random
   
8. """
   
9. 
   
10. class Solution:
    
11.     def copyRandomList(self, head: 'Node') -> 'Node':
    
12.         if head == None: return head
    
13.         hashmap = collections.defaultdict(Node)
    
14.         curt = head
    
15.         
    
16.         while curt:
    
17.             new_node = Node(curt.val)
    
18.             hashmap[curt] = new_node
    
19.             curt = curt.next
    
20.         
    
21.         curt = head
    
22.         
    
23.         while curt:
    
24.             next = curt.next
    
25.             random = curt.random
    
26.             
    
27.             if next != None:
    
28.                 hashmap[curt].next = hashmap[next]
    
29.             if random != None:
    
30.                 hashmap[curt].random = hashmap[random]
    
31.             curt = curt.next
    
32.         
    
33.         return hashmap[head]

复制代码