[leetcode] 138. Copy List with Random Pointer

문제 설명

링크
next 와 random 포인터를 가진 linked list 를 deepcopy 하는 문제

접근 - dictionary

• dict[originalNode] = copiedNode
• 딕셔너리를 만들면서 next 연결
• 딕셔너리를 이용해 random 연결

코드 1

class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        tmp = head
        res = ptr = None
        n = 0
        newList = {None: None}
        while tmp:
            newNode = Node(tmp.val)
            newList[tmp] = newNode
            if n == 0:
                res = newNode
                ptr = res
            else:
                ptr.next = newNode
                ptr = ptr.next
                
            tmp = tmp.next
            
            n += 1
        ptr = res
        
        while head:
            ptr.random = newList[head.random]
            ptr = ptr.next
            head = head.next

        return res

코드 2

• 딕셔너리 다 만들고 next 와 random 동시에 연결
• 깔끔함
• leetcode discussion참고

class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        tmp = head
        res = ptr = None
        n = 0
        newList = {None: None}
        while tmp:
            newNode = Node(tmp.val)
            newList[tmp] = newNode
                
            tmp = tmp.next
            
            n += 1
        tmp = head
        
        while tmp:
            newList[tmp].next = newList[tmp.next]
            newList[tmp].random = newList[tmp.random]
            tmp = tmp.next

        return newList[head]