138. Copy List with Random Pointer

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

Return a deep copy of the 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) where random pointer points to, or null if it does not point to any node.

역대급으로 뭔소린지 모르겠는 문제..

왜 굳이 random 이 있고 그런건지...?

First Idea

"""
# 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: 'Node') -> 'Node':
        if head is None: return None
        copyList = Node(0)
        temp = head
        temp2 = copyList
      
        while temp:
            newNode = Node(temp.val, temp.next, None)
            temp2.next = newNode
            temp = temp.next
            temp2 = temp2.next
       
        # random 노드를 가리키게 하려면
        # head 에 대응하는 값을 copyList 에서 찾아야 함..

우선 복사 자체를 해보려고 했는데.. random 값 넣는 과정에서.. 잘 안되네요
linked 말고 걍 리스트로 풀고 싶다...☆

Solution 1: Runtime: 28 ms - 96.30% / Memory Usage: 14.6 MB - 98.68%

"""
# 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: 'Node') -> 'Node':
        if head is None: return None
        mapping = {}
        cur = head
        while cur:
            mapping[cur] = Node(cur.val,None,None)
            cur = cur.next
        cur = head
        while cur:
            if cur.next:
                mapping[cur].next = mapping[cur.next]
            if cur.random:
                mapping[cur].random = mapping[cur.random]
            cur = cur.next
        return mapping[head]

mapping 이라는 딕셔너리를 만들어서

우선 val 값들로 노드를 만들어 저장해준다. - 첫번째 반복문
그 다음에 next 와 random 값이 있으면 저장해준다. - 두번째 반복문

마지막으로 mapping[head] 를 리턴하면 head 를 deep copy 한 결과가 됨

솔루션을 보니까 문제 의도가 대충 이해가 되는거 같기도..
random 이 어딜 가리킬지 모르니까 순서대로 노드 생성하긴 힘든 상황을 어떻게 풀것인지 묻는 문제인듯

딕셔너리 외우자!!