138. Copy List with Random Pointer

138. Copy List with Random Pointer

 

https://youtu.be/5Y2EiZST97Y?si=24I-c_Obsw9-9vYx

 

"""
# 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]':
        if not head:
            return None  # 빈 리스트라면 None을 반환

        # Step 1: 원본 노드와 복사본 노드 간 매핑 생성
        old_to_new = {}  # {원본 노드: 복사된 노드}를 저장할 딕셔너리
        current = head  # 리스트의 첫 번째 노드부터 순회 시작
        while current:
            # 현재 노드를 복사하고 매핑에 추가
            old_to_new[current] = Node(current.val)
            current = current.next  # 다음 노드로 이동

        # Step 2: 복사된 노드에 next와 random 포인터 설정
        current = head  # 다시 첫 번째 노드부터 순회 시작
        while current:
            # 복사된 노드의 next 포인터 설정
            if current.next:
                old_to_new[current].next = old_to_new[current.next]
            
            # 복사된 노드의 random 포인터 설정
            if current.random:
                old_to_new[current].random = old_to_new[current.random]
            
            current = current.next  # 다음 노드로 이동

        # Step 3: 복사된 리스트의 헤드 반환
        return old_to_new[head]  # 복사된 첫 번째 노드 반환