LeetCode | 138. Copy List with Random Pointer

문제

길이 n의 연결리스트가 주어집니다. 각 노드들은 리스트의 랜덤 노드 혹은 null을 가리킬 수 있는 random 포인터를 추가로 갖습니다.

리스트의 깊은 복사본(deep copy)을 구성하세요.

딥 카피는 정확히 n개의 새로운 노드로 구성되어야 하며, 각 새 노드의 값은 해당 원본 노드의 값으로 설정됩니다. 새 노드의 next 포인터와 random 포인터 모두 복사된 목록의 새 노드를 가리키도록 해서, 원본 리스트와 복사한 리스트의 포인터가 같은 상태여야 합니다. 새 리스트의 포인터 중 어떤 것도 원본 리스트의 노드를 가리켜서는 안 됩니다.

예를 들어, 원본 리스트에 X 와 Y 노드가 있고, X.random --> Y 라면, 그에 상응하는 복사한 리스트의 x 와 y 역시 x.random --> y 여야 합니다.

복사한 연결리스트의 헤드를 반환하세요.

연결리스트는 input/output에서 n개의 노드 리스트로 표시됩니다. 각 노드는 [val, random_index] 쌍으로 표현됩니다:

val: Node.val을 나타내는 정수
random_index: random 포인터가 가리키는 노드의 인덱스(0~n-1 범위), 노드를 가리키지 않는 경우 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

풀이¹

Hash Map 방식

class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        if not head:
            return None
        old_to_new = {}

        curr = head
        while curr:
            old_to_new[curr] = Node(curr.val)
            curr = curr.next

        curr = head
        while curr:
            old_to_new[curr].next = old_to_new.get(curr.next)
            old_to_new[curr].random = old_to_new.get(curr.random)
            curr = curr.next

        return old_to_new[head]

Time Complexity: O(n) 각 노드를 2번 방문

Space Complexity: O(n) hash map 사용

Interweaving Nodes 방식

class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        if not head:
            return None

        curr = head
        while curr:
            new_node = Node(curr.val, curr.next)
            curr.next = new_node
            curr = new_node.next

        curr = head
        while curr:
            if curr.random:
                curr.next.random = curr.random.next
            curr = curr.next.next

        old_head = head
        new_head = head.next
        curr_old = old_head
        curr_new = new_head

        while curr_old:
            curr_old.next = curr_old.next.next
            curr_new.next = curr_new.next.next if curr_new.next else None
            curr_old = curr_old.next
            curr_new = curr_new.next

        return new_head