← Hash Strategies

Micro-Drill #137 — Clone linked list with random

Hash Strategies Target: 15s

Two-pass hash map maps old nodes to new clones. Second pass wires next/random.

d = {None: None}
n = head
while n:
    d[n] = Node(n.val)
    n = n.next
n = head
while n:
    d[n].next = d[n.next]
    d[n].random = d[n.random]
    n = n.next

Type it from memory. Go.

Practice Problems

• 138. Copy List with Random Pointer
• 133. Clone Graph

Related Coding Drills

• Drill #137 — Copy List with Random Pointer Medium
• Drill #11 — Reverse a linked list Easy
• Drill #99 — Clone graph Medium