⚡Flashcard Drill➔
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

  1. First pass: create a copy of every node and store the mapping original -> copy in a hash map.
  2. Second pass: wire up next and random using the map.
  3. Two passes avoid the interleaving trick (which is O(1) space but harder to get right).
  4. The map is the key: without it, resolving a random pointer 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(): a None key would raise a KeyError.
  • Copying only the values: the random pointers must reproduce the structure, which requires the node mapping.
  • Assuming random never 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.
🎯 Drill This Card Now➔

🧩 Related Linked List Problems