[DSA][Linked List] 06. Copy List with Random Pointer

LeetCode 138

 

06. Copy List with Random Pointer

A linked list of length n is given such that each node contains an additional random pointer, which could point to any node in the list, or null.

Construct a deep copy of the list.
The deep copy should consist of exactly n brand new nodes, where each new node has its value set to the value of its corresponding original node.
Both the next and random pointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state.
None of the pointers in the new list should point to nodes in the original list.

For example, if there are two nodes X and Y in the original list, where X.random --> Y,
then for the corresponding two nodes x and y in the copied list, x.random --> y.

Return the head of the copied linked list.
The linked list is represented in the input/output as a list of n nodes.
Each node is represented as a pair of [val, random_index] where:
- val: an integer representing Node.val
- random_index: the index of the node (range from 0 to n-1) that the random pointer points to, or null if it does not point to any node.
Your code will only be given the head of the original linked list.

 

 

[질문하기]

- 랜덤 포인터와 next 포인터는 항상 1:1 매칭이 되나요? NO

- 노드의 val에 중복된 값이 있을 수 있나요?

 

 

[아이디어]

- HashMap을 사용해서 복사 노드를 생성하자.

- random과 next의 관계를 하나씩 복사 노드에 대체하자.

 

 

[풀이 1] Hash Map

class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        oldToCopy = collections.defaultdict(lambda: Node(0))
        oldToCopy[None] = None
        
        cur = head
        while cur:
            oldToCopy[cur].val = cur.val
            oldToCopy[cur].next = oldToCopy[cur.next]
            oldToCopy[cur].random = oldToCopy[cur.random]
            cur = cur.next
        return oldToCopy[head]

이 문제가 어려운 이유는, 원본 리스트를 순회하면서 노드를 하나씩 복사할 때, 어떤 노드의 random 포인터가 가리키는 노드는 아직 복사되지 않았을 수 있기 때문이다. 이 상황을 해결하기 위해 Hash Map(또는 Dictionary)을 사용하여, 원본 노드를 키로, 복사 노드를 값으로 저장한다. 특히 defaultdict를 사용하면, 복사 노드가 아직 없더라도 자동으로 Node(0)을 생성해 주기 때문에, 먼저 포인터 연결을 해두고 나중에 순회하면서 실제 값을 할당할 수 있다. 이렇게 하면 모든 노드를 한 번만 순회하면서 next와 random 포인터가 올바르게 설정된 복사 연결 리스트를 만들 수 있다.

 

위와 같은 연결리스트가 있다고 가정하자.

 

STEP 1) oldToCopy[cur].val = cur.val

우선 oldToCopy[cur]이 존재하지 않으므로 defaultdict에 의해 Node(0)을 생성하고 mapping 시켜준다.

그 후 oldToCopy[cur].val을 cur.val로 업데이트해 준다.

 

STEP 2) oldToCopy[cur].next = oldToCopy[cur.next]

oldToCopy[cur.next]가 존재하지 않으므로 defaultdict에 의해 Node(0)을 생성하고 mapping 시켜준다.

 

 

그 후 oldToCopy[cur].next을 oldToCopy[cur.next] 로 업데이트해 준다.

 

STEP 3) oldToCopy[cur].random = oldToCopy[cur.random]

cur.random은 None인데, None은 명시적으로 oldToCopy[None] = None으로 설정했기 때문에 oldToCopy[cur].random = None으로 설정된다.

 

이 과정을 각 노드에 대해 반복하면서, 노드가 없다면 Copy 노드를 생성해 두고 이미 생성됐다면 값(val, next, random 등)을 설정한다.

 

⏱️ 시간복잡도

연결 리스트의 노드 전체를 순회해야 하므로, 노드 수를 n이라 할 때 시간 복잡도는 O(n)이다.

🧠 공간복잡도

노드의 매핑 정보를 전부 저장해야 하기 때문에 공간 복잡도는 O(n)이다.

 

 

[풀이 2] Linked List

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

        l1 = head
        while l1:
            l2 = Node(l1.val)
            l2.next = l1.random
            l1.random = l2
            l1 = l1.next
        
        newHead = head.random
        
        l1 = head
        while l1:
            l2 = l1.random
            l2.random = l2.next.random if l2.next else None
            l1 = l1.next
            
        l1 = head
        while l1 is not None:
            l2 = l1.random
            l1.random = l2.next
            l2.next = l1.next.random if l1.next else None
            l1 = l1.next

        return newHead

첫 번째 방식이 HashMap을 사용해서 원복 노드와 복사 노드를 mapping 시켰다면, 이 방식은 복사 노드를 따로 저장하지 않기 위해, 원본 노드의 random에 복사 노드를 임시 저장하고, 복사 노드의 next에 원래의 random을 저장한 뒤, 이를 기반으로 복사본의 random과 next를 설정하고 마지막에 원본을 복원한다.

 

STEP 1) 복사 노드를 만들고 원본 노드의 random 관계를 원본 - 복사 - 원본의 random 관계로 분리

초록색 선을 random의 관계라고 한다면, A → B → C의 연결 리스트에서

A → C (random)의 관계를 A → A' → C로 중간에 복사 노드를 슬쩍 끼워 넣는 것이다.

As Is  	  To Be
A → C	A → A' → C 
B → A	B → B' → A
C → B	C → C' → B
  ↑       ↑    ↑
random random next

여기서 To Be의 앞의 화살표는 원본 노드의 random, 뒤의 화살표는 복사 노드의 next이다.

 

STEP 2) 복사 노드의 random 관계를 기존 노드의 random 노드와 같게 설정

기존 random 관계 A → C를 A' → C'로 복사하고 싶기 때문에, A'의 random이 가리키는 노드를 A' → C (next), C → C' (random)의 관계를 사용해서 만들어준다.

 

STEP 3) 원본 노드의 random 관계를 복구하고 복사 노드의 next 설정

마지막으로 A →  A' (random), A' → C (next)로 저장해 둔 관계를 이용해서 기존의 random 관계를 A → C로 복구하고,

기존의 next 관계 A → B를  A' → B'로 복사하고 싶기 때문에, A'의 next가 가리키는 노드를 A → B (next), B → B' (random)의 관계를 사용해서 만들어준다.

 

 

⏱️ 시간복잡도

연결 리스트의 노드 전체를 순회해야 하므로, 노드 수를 n이라 할 때 시간 복잡도는 O(n)이다.

🧠 공간복잡도

노드의 매핑 정보 등의 추가 공간을 사용하지 않기 때문에 공간 복잡도는 O(1)이다.