[Leetcode] 138. Copy List with Random Pointer

문제 바로가기

Time Complexity: $O(n)$
Space Complexity: $O(n)$

Recursion

"""
# 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':
        hashT = dict()
        def DFS(head: 'Node'):
            if head is None:
                return
            
            if head not in hashT:
                hashT[head] = Node(head.val)
                hashT[head].next = DFS(head.next)
                hashT[head].random = DFS(head.random)
                
            return hashT[head]
        
        return DFS(head)

Recursion

"""
# 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

        cur = head
        hashT = { head: Node(head.val) }
        while cur:
            if cur.next:
                if cur.next not in hashT:
                    hashT[cur.next] = Node(cur.next.val)
                hashT[cur].next = hashT[cur.next]
            if cur.random:
                if cur.random not in hashT:
                    hashT[cur.random] = Node(cur.random.val)
                hashT[cur].random = hashT[cur.random]
            cur = cur.next
        
        return hashT[head]