← 전체 회차
A-039● Day 392026.06.14mediumleetcode #138neetcode150

랜덤 포인터가 있는 리스트 복사

#hash-table#linked-list
↗ leetcode #138 · copy-list-with-random-pointer
01

문제

· problem
P.039

랜덤 포인터가 있는 리스트 복사

↗ leetcode #138

각 노드에 random 포인터가 추가된 길이 n인 링크드 리스트가 주어집니다. random 포인터는 리스트의 어떤 노드를 가리킬 수도 있고, null을 가리킬 수도 있습니다. 리스트의 깊은 복사본(deep copy)을 구성하세요. 깊은 복사본은 정확히 n개의 완전히 새로운 노드로 구성되어야 하며, 각 새 노드의 값은 대응하는 원본 노드의 값으로 설정되어야 합니다. 새 노드의 next와 random 포인터는 모두 복사된 리스트의 새 노드를 가리켜야 하므로, 원본 리스트의 포인터와 복사된 리스트의 포인터가 동일한 리스트 상태를 나타냅니다. 새 리스트의 어떤 포인터도 원본 리스트의 노드를 가리키면 안 됩니다. 예를 들어, 원본 리스트에 X와 Y 두 개의 노드가 있고 X.random --> Y인 경우, 복사된 리스트의 대응하는 두 노드 x와 y에 대해 x.random --> y이어야 합니다.

제약
  • · 0 ≤ n ≤ 1000
  • · -10⁴ ≤ Node.val ≤ 10⁴
  • · Node.random is null or points to some node in the linked list
// 지문은 본인 언어 요약 — 원문은 위 링크에서
입출력 예시
example 1input → output
[[7,null],[13,0],[11,4],[10,2],[1,0]]
[[7,null],[13,0],[11,4],[10,2],[1,0]]
example 2input → output
[[1,1],[2,1]]
[[1,1],[2,1]]
example 3input → output
[[3,null],[3,0],[3,null]]
[[3,null],[3,0],[3,null]]
02

사전 사고

· pre-solve
● 1리스트 출력→● 2선택→● 3정답 공개
  • ☐
    빈 리스트(head = None)를 처리해야 하나요?
  • ☐
    한 노드의 random 포인터가 자신을 가리킬 수 있나요?
  • ☐
    random 포인터가 null일 수 있나요?
  • ☐
    새 노드의 포인터가 원본 노드를 가리켜도 되나요?
  • ☐
    원본 리스트를 수정해도 되나요?
  • ☐
    O(n) 공간보다 더 적은 공간을 사용할 수 있나요?
  • ☐
    딕셔너리 대신 다른 자료구조를 사용할 수 있나요?
던질 질문에 체크하고 확인을 누르세요
// 결과는 세션 메모리만 — 새로고침하면 초기화됩니다 (반복 학습)
03

논리 구조

· logic
● 1슬롯 출력→● 2슬롯별 선택→● 3정답 공개
// 각 슬롯에 들어갈 코드 한 줄을 골라 알고리즘 흐름을 합성해보세요. 코드는 안 짜지만 논리 뼈대는 직접.
step 1· None을 포함한 매핑 초기화
○
oldToCopy = {None: None}
○
oldToCopy = {}
○
oldToCopy = {head: None}
step 2· 첫 번째 패스: 모든 복사 노드 생성
○
while cur:
○
while cur.next:
○
while cur is not None:
step 3· 복사 노드 생성│ 중첩
○
copy = Node(cur.val)
○
copy = Node(cur)
○
copy = cur
step 4· 원본-복사본 매핑 저장│ 중첩
○
oldToCopy[cur] = copy
○
oldToCopy[copy] = cur
○
oldToCopy[cur.val] = copy
step 5· 두 번째 패스: 포인터 설정
○
while cur:
○
while cur.next:
○
while cur:
step 6· next 포인터를 매핑으로 설정│ 중첩
○
copy.next = oldToCopy[cur.next]
○
copy.next = cur.next
○
copy.next = oldToCopy.get(cur.next)
step 7· random 포인터를 매핑으로 설정│ 중첩
○
copy.random = oldToCopy[cur.random]
○
copy.random = cur.random
○
copy.random = oldToCopy[cur].random
각 슬롯에 한 줄씩 골라보세요
// format: slot — 다른 패턴(재귀·DP 등) 은 ordering·state-first 등 별도 format. ADR-08 후속.
04

문제풀이 · 트레이스

· solve
solution.py
1
"""
2
# Definition for a Node.
3
class Node:
4
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
5
        self.val = int(x)
6
        self.next = next
7
        self.random = random
8
"""
9
10
11
class Solution:
12
    def copyRandomList(self, head: "Node") -> "Node":
13
        oldToCopy = {None: None}
14
15
        cur = head
16
        while cur:
17
            copy = Node(cur.val)
18
            oldToCopy[cur] = copy
19
            cur = cur.next
20
        cur = head
21
        while cur:
22
            copy = oldToCopy[cur]
23
            copy.next = oldToCopy[cur.next]
24
            copy.random = oldToCopy[cur.random]
25
            cur = cur.next
26
        return oldToCopy[head]
머릿속 dry-run 케이스
// 각 케이스를 머릿속으로 따라가보세요. 막히면 아래 worked example 펼침.
case 1
[[7,null],[13,0],[11,4],[10,2],[1,0]]
→
[[7,null],[13,0],[11,4],[10,2],[1,0]]
case 2
[[1,1],[2,1]]
→
[[1,1],[2,1]]
case 3
[[3,null],[3,0],[3,null]]
→
[[3,null],[3,0],[3,null]]
// UI 가 walk-through 안 함 — 학습자가 머릿속으로. 막히면 worked example 펼침.