임의 포인터로 목록 복사

길이가 n인 연결 목록이 제공되어 각 노드가 목록의 모든 노드 또는 null를 가리킬 수 있는 추가 임의 포인터를 포함합니다.

목록의 deep copy을 구성합니다. 딥 카피는 정확히 n개의 새로운 노드로 구성되어야 하며, 각각의 새 노드에는 해당하는 원래 노드의 값으로 설정된 값이 있습니다. 새 노드의 next 및 random 포인터는 원본 목록과 복사된 목록의 포인터가 동일한 목록 상태를 나타내도록 복사된 목록의 새 노드를 가리켜야 합니다. 새 목록의 어떤 포인터도 원래 목록의 노드를 가리켜서는 안 됩니다.

예를 들어 원래 목록에 두 개의 노드 X 및 Y가 있는 경우 (여기서 X.random --> Y) 복사된 목록의 해당 두 노드 x 및 y에 대해 x.random --> y 입니다.

복사된 연결 목록의 헤드를 반환합니다.

연결된 목록은 입력/출력에서 n 노드 목록으로 표시됩니다. 각 노드는 [val, random_index] 쌍으로 표시됩니다.

val : Node.val를 나타내는 정수

random_index : 0 포인터가 가리키는 노드의 인덱스(범위는 n-1에서 random까지), 또는 어떤 노드도 가리키지 않는 경우 null입니다.

귀하의 코드는 원래 연결된 목록의 head만 제공됩니다.

예 1:



입력: 헤드 = [[7,null],[13,0],[11,4],[10,2],[1,0]]
출력: [[7,null],[13,0],[11,4],[10,2],[1,0]]

예 2:



입력: 헤드 = [[1,1],[2,1]]
출력: [[1,1],[2,1]]

예 3:



입력: 헤드 = [[3,null],[3,0],[3,null]]
출력: [[3,null],[3,0],[3,null]]

제약:

0 <= n <= 1000

-104 <= Node.val <= 104

Node.random는 null이거나 연결된 목록의 일부 노드를 가리키고 있습니다.

해결책:

"""
# 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 copy(self, head):
        newhead = None
        if head:
            newhead = self.visited.get(head, Node(head.val))
            self.visited[head] = newhead
            if head.random != None:
                newhead.random = self.visited.get(head.random, Node(head.random.val))
                self.visited[head.random] = newhead.random
            newhead.next = self.copy(head.next)
        return newhead

    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        self.visited = {}
        return self.copy(head)