NeetCode #324LC-138MediumLinked ListNC 150NC 250
← Back to All Problems#324 · #138 · Copy List with Random Pointer(复制带随机指针的链表)
📌 Problem Statement & Constraints
A linked list has nodes with an extra
random pointer that may point to any node or None. Return a deep copy of the list: new nodes, with next and random pointers reproducing the original structure. Constraints: 0 <= n <= 1000.💡 Core Algorithmic Approaches
- First pass: create a copy of every node and store the mapping
original -> copyin a hash map. - Second pass: wire up
nextandrandomusing the map. - Two passes avoid the interleaving trick (which is O(1) space but harder to get right).
- The map is the key: without it, resolving a
randompointer would require a search.
💻 Benchmark Python3 Implementation
class Solution:
def copyRandomList(self, head: "Optional[Node]") -> "Optional[Node]":
if not head:
return None
# pass 1: copy every node, remember the mapping
mapping = {}
cur = head
while cur:
mapping[cur] = Node(cur.val)
cur = cur.next
# pass 2: wire next and random
cur = head
while cur:
mapping[cur].next = mapping.get(cur.next) # None-safe
mapping[cur].random = mapping.get(cur.random)
cur = cur.next
return mapping[head]⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): two passes with O(1) map operations.
💾 Space Complexity
O(n) for the mapping. The interleaving variant achieves O(1) extra space by weaving the copies into the original list.
⚠️ Interview Pitfalls & Follow-ups
- Using
mapping[cur.next]instead of.get(): aNonekey would raise aKeyError. - Copying only the values: the
randompointers must reproduce the structure, which requires the node mapping. - Assuming
randomnever points backwards: it can point to any node, including earlier ones -- which is exactly why the map is built first. - Trying to deep-copy with
copy.deepcopy: it would follow the pointers and copy the whole graph, but the resulting node types and structure are not guaranteed to match the expected interface.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.