leetcode medium : Copy List with Random Pointer

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

LeetCode - The World's Leading Online Programming Learning Platform

 

linked list를 딥카피 하는 문제인데 문제는 카피된 리스트가 기존 리스트의 노드를 가리키면 안된다는 것.

next랑 random같은 포인터를(편의상 포인터라고 칭함) 복사할때는 반드시 카피되는 새 리스트의 노드를 가리켜야된다.

그렇기 때문에 복사하기 전에 미리 노드를 다 만들어두고 매핑을 해둘 필요가 있다.

two scan으로 쉽게 풀었다.

"""
# 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]':
        sourceDummy = Node(0, head, None)
        destDummy = Node(0, None, None)

        sp = sourceDummy
        dp = destDummy

        srcToDest = {None: None}

        while True:
            if not sp.next:
                break

            dp.next = Node(sp.next.val)
            srcToDest[sp.next] = dp.next

            sp = sp.next
            dp = dp.next

        sp = sourceDummy
        dp = destDummy

        while True:
            if not sp.next:
                break

            sp = sp.next
            dp = dp.next

            dp.next = srcToDest[sp.next]
            dp.random = srcToDest[sp.random]

        return destDummy.next

시간복잡도 O(N)

공간복잡도 O(N)