[Leetcode 138] - Copy List with Random Pointer w/ Python

Problem Description

 

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), 랜덤(Random) 포인터가 있는 연결 리스트가 주어진다.

이를 Deep Copy해서 Input과 같은 리스트를 Output 하라는 문제네요.

 

 

https://leetcode.com/problems/copy-list-with-random-pointer/description/

 

 

---

 

Examples - 예시

 

Example 1

 

Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]

 

 

 

Example 2

 

Input: head = [[1,1],[2,1]]
Output: [[1,1],[2,1]]

 

 

 

---

 

풀이

핵심은 리스트를 두번 훑어야 된다는것

1. Next와 Random 포인터가 어디를 향하는지 먼저 저장

2. 새로운 연결 리스트를 만들기

 

So...

1. 첫 루프: HashMap을 통해 각 노드 Mapping

2. 다음 루프: 노드를 찾아서 포인터 설정

 

class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        # 루프때 멈추는 컨디션은 노드가 None이 아닐때
        # 몇개 노드는 None으로 포인트하는 경우가 있기에 미리 맵에 저장
        copyMap = { None: None }
        
        curr = head
        while curr:
            copy = Node(curr.val) # 현재 curr 포인터에 위치한 노드 카피
            # 해시맵에 저장 {노드(val, next, random) : 노드(val)}
            copyMap[curr] = copy
            curr = curr.next # 다음 노드 확인하러 가즈아
        
        curr = head # 이제 맵에 모든 노드가 저장 되어 있음
        while curr:
            copy = copyMap[curr] # 현제 노드를 맵에서 찾아서
            copy.next = copyMap[curr.next] # 다음 노드 확인, Next 포인터에 저장
            copy.random = copyMap[curr.random] # 다음 노드 확인, 랜덤 포인터에 저장
            curr = curr.next # 답 확인하러 가즈아
        
        return copyMap[head] # 맵에 있는 head를 찾아서 그 노드를 리턴한다

 

 

 

아까 30 ms라면서... ㅠ