138. Copy List with Random Pointer (Hash Table, Linked List)

링크 - https://leetcode.com/problems/copy-list-with-random-pointer/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Medium

Intuition

우리는 iterative한 방법을 사용해 O(1) space를 활용하여 문제를 풀 수 있다. 

1. 먼저 head가 없거나 None이면, 그냥 head를 반환하고 끝낸다.

2. ptr을 head로 초기에 지정해준다.

3. new_node = Node(ptr.val, None, None)을 해서 새로운 노드를 만든다.

4. 그다음 new_node.next = ptr.next, ptr.next = new_node, ptr = new_node.next를 해서 원래있던 node사이에 new_node를 집어넣고 다음 node로 ptr를 움직인다.

5. 3,4를 반복하면 우리는 A-> A' -> B -> B' -> C -> C' 같은 linked list가 만들어진다.

6. ptr을 head로 지정해준다. 그 다음, ptr.next.random = ptr.random.next if ptr.random else None을 통해 각 노드에서 새로만든 노드들에게 random포인터를 지정해준다. 그리고는 ptr = ptr.next.next를 통해 ptr를 움직인다.

7. 6번을 끝내면 모든 새로만든 노드들도 random 포인터를 가리키게 된다.

8. old node들과 new node들을 분리시킨다.

Code

# Solution with O(N) space
"""
# 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: 'Optional[Node]') -> 'Optional[Node]':
        if not head:
            return head
        dummy_node = Node(-1)
        new_head = Node(-1)
        dummy_node.next = new_head

        new_node = dummy_node.next
        node = head
        hash_table = {}
        while node:
            new_node.val = node.val
            hash_table[node] = new_node

            if node.next:
                new_next_node = Node(-1)
                new_node.next = new_next_node

            node = node.next
            new_node = new_node.next

        node = head
        new_node = dummy_node.next
        while node:
            if node.random:
                new_node.random = hash_table[node.random]
            node = node.next
            new_node = new_node.next

        return dummy_node.next
        
# Solution with O(1) space
class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        if not head:
            return head

        node = head
        while node:
            new_node = Node(node.val, None, None)
            
            new_node.next = node.next
            node.next = new_node
            node = node.next.next

        node = head
        while node:
            if node.random:
                node.next.random = node.random.next
            node = node.next.next

        new_head = head.next
        new_node = head.next
        while new_node:
            if new_node.next:
                new_node.next = new_node.next.next
            new_node = new_node.next

        return new_head

Complexity

Time Complexity: O(N)

Space Complexity: O(1)