#138

Copy List with Random Pointer

specialist · 680 · lc medium +30 · failed · 62.5% accepted · 15,469 likes · top 64%

Description

A linked list of length n is given; each node holds an extra random pointer that may point to any node in the list or to null.

Produce a deep copy of the list — a brand-new list of n nodes where each new node's value, next pointer, and random pointer mirror those of the corresponding original node. No pointer in the copy may reference a node from the original list.

Return the head of the copied list.

The list is encoded as n pairs [val, random_index] where:

- val: the node's integer value.

- random_index: the 0-based index of the node targeted by random, or null if none.

Your code receives only the head of the original list.

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]]

Code

"""
# 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: 'Optional[Node]') -> 'Optional[Node]':

"""
# 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: 'Optional[Node]') -> 'Optional[Node]':