Leetcode 138. Copy List with Random Pointer
本帖最后由 Seawolf 于 2020-9-16 03:54 编辑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 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 = [,,,,]
Output: [,,,,]
Example 2:
Input: head = [,]
Output: [,]
Example 3:
Input: head = [,,]
Output: [,,]
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.
"""
# Definition for a Node.
class Node:
def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
self.val = int(x)
self.next = next
self.random = random
"""
class Solution:
def copyRandomList(self, head: 'Node') -> 'Node':
if head == None: return head
hashmap = collections.defaultdict(Node)
curt = head
while curt:
new_node = Node(curt.val)
hashmap = new_node
curt = curt.next
curt = head
while curt:
next = curt.next
random = curt.random
if next != None:
hashmap.next = hashmap
if random != None:
hashmap.random = hashmap
curt = curt.next
return hashmap
页:
[1]