[LeetCode 해석 및 풀이] 138. Copy List with Random Pointer

LeetCode 문제 해석 및 풀이 방법

 

문제 138. 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 n1) 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.

 

한글

원래 리스트 깊은 복사하라는 뜻이다. 랜덤 포인터와 함께

 

제한조건

• 0 <= n <= 1000
• -10^4 <= Node.val <= 10^4
• Node.random is null or is pointing to some node in the linked list.

 

입출력 예

입력	출력
리스트	입력과 같은데 새로운 노드로 만들어진 리스트

 

 

해답 및 해설

파이썬 (Python)

class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        old_now_node = head
        while old_now_node:
            new_node = Node(old_now_node.val, old_now_node.next, old_now_node.random)
            old_now_node.next = new_node
            old_now_node = new_node.next

        new_now_node = head.next
        while new_now_node:
            new_now_node.random = getattr(new_now_node.random, 'next', None)
            if new_now_node.next:
                new_now_node = new_now_node.next.next
            else:
                new_now_node = None

        dummy_old_head = old_list = Node(0)
        dummy_new_head = new_list = Node(0)
        now_node = head

        while now_node:
            old_list.next = now_node
            new_list.next = now_node.next

            old_list = old_list.next
            new_list = old_list.next
            now_node = now_node.next.next
        old_list.next = None

        return dummy_new_head.next

다음과 같은 과정을 거친다.

1. 원래 리스트를 순회하면서 새로운 노드를 만들어준다. 노드의 값, 다음 노드, 랜덤 노드는 이전과 똑같이 만든다. 그 후 새로 만든 노드를 이전 노드의 다음에다가 붙인다.
   과정이 완료되면 노드의 순서는 다음과 같이 된다. (프라임이 있는게 새로운 노드)
   A →  A` →  B → B ` → C → C `
2. 새로운 노드들은 현재 랜덤 노드가 옛날 노드들과 연결되어 있는 상태이다. 새로운 노드들만 순회하면서 랜덤 노드가 새로운 노드로 연결되도록 바꾸어준다. 새로운 노드는 옛날 노드의 바로 다음에 있으므로 쉽게 재연결해줄 수 있다.
3. 마지막으로 하나의 연결된 리스트를 옛날 리스트와 새 리스트로 분리해준다. 노드를 2개씩 떼어서 각기 다른 곳에 붙여주면 된다.