138. Copy List with Random Pointer

[zeikar]

Problem link

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

Problem Summary

랜덤 포인터가 있는 링크드 리스트를 그대로 복사하는 문제

Solution

죽 돌면서 복사하면 된다. 랜덤 포인터의 경우 map으로 random 노드를 관리해주면 된다.

Source Code

# Definition for a Node.
from typing import Optional


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 None

        new_head = Node(head.val)

        node_map = {head: new_head}

        node = head.next
        prev = new_head

        while node:
            new_node = Node(node.val)
            prev.next = new_node
            node_map[node] = new_node
            prev = new_node
            node = node.next

        node = head
        prev = new_head
        while node:
            if node.random:
                prev.random = node_map[node.random]
            prev = prev.next
            node = node.next

        return new_head