← all entries
A-039● Day 392026.06.14mediumleetcode #138neetcode150

Copy List with Random Pointer

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

Problem

· problem
P.039

Copy List with Random Pointer

↗ leetcode #138

A linked list of length n is given such that each node contains an additional random pointer, which could point to any node in the list, or null. Construct a deep copy of the list. The deep copy should consist of exactly n brand new nodes, where each new node has its value set to the value of its corresponding original node. Both the next and random pointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state. None of the pointers in the new list should point to nodes in the original list. For example, if there are two nodes X and Y in the original list, where X.random --> Y, then for the corresponding two nodes x and y in the copied list, x.random --> y.

constraints
  • · 0 ≤ n ≤ 1000
  • · -10⁴ ≤ Node.val ≤ 10⁴
  • · Node.random is null or points to some node in the linked list
// paraphrased summary — see source for full text
examples
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

· pre-solve
● 1list shown→● 2select→● 3reveal
  • ☐
    Do we need to handle an empty list (head = None)?
  • ☐
    Can a node's random pointer point to itself?
  • ☐
    Can a node's random pointer be null?
  • ☐
    Can new_node pointers point to original nodes?
  • ☐
    Can we modify the original list?
  • ☐
    Can we solve this with less than O(n) space?
  • ☐
    Can we use a different data structure instead of a hash map?
check the items you would ask, then press confirm
// session-only state — refresh resets (repeatable practice)
03

Logic Structure

· logic
● 1slots shown→● 2pick per slot→● 3reveal
// pick one code line per slot to assemble the algorithm flow. no typing — just the logic skeleton.
step 1· Initialize mapping with None key
○
oldToCopy = {None: None}
○
oldToCopy = {}
○
oldToCopy = {head: None}
step 2· First pass: create all copy nodes
○
while cur:
○
while cur.next:
○
while cur is not None:
step 3· Create copy node│ nested
○
copy = Node(cur.val)
○
copy = Node(cur)
○
copy = cur
step 4· Store original-to-copy mapping│ nested
○
oldToCopy[cur] = copy
○
oldToCopy[copy] = cur
○
oldToCopy[cur.val] = copy
step 5· Second pass: set next and random pointers
○
while cur:
○
while cur.next:
○
while cur:
step 6· Set next pointer using mapping│ nested
○
copy.next = oldToCopy[cur.next]
○
copy.next = cur.next
○
copy.next = oldToCopy.get(cur.next)
step 7· Set random pointer using mapping│ nested
○
copy.random = oldToCopy[cur.random]
○
copy.random = cur.random
○
copy.random = oldToCopy[cur].random
pick one option per slot
// format: slot — recursive / DP patterns use ordering / state-first formats. ADR-08 follow-up.
04

Solve · Trace

· 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]
mental dry-run cases
// walk each case in your head; expand the worked example below if stuck.
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 does not walk-through — you do the dry-run mentally. Expand the worked example if stuck.