loading

Copy List with Random Pointer — Step-by-Step Visualization

mediumLeetCode #138Hash TableLinked List

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.

Algorithm Pattern

Hash Map Mapping

Key Idea

To deep copy a linked list where nodes have pointers to other nodes that might not have been created yet, we use a Hash Map. In the first pass, we create all the new copy nodes and store the mapping from `original_node` to `copy_node`. In the second pass, we assign the `next` and `random` pointers of each copy node by looking up the corresponding pointers of the original nodes in our map.

Step-by-Step Approach

  1. Initialize an empty Hash Map `oldToNew`.
  2. First pass: Iterate through the original list, create a copy of each node, and store the mapping `oldNode -> newNode`.
  3. Second pass: Iterate again, for each `oldNode`, set `oldToNew[oldNode].next = oldToNew[oldNode.next]` and `oldToNew[oldNode].random = oldToNew[oldNode.random]`.
  4. Return `oldToNew[head]`.

Common Gotchas

  • The random pointer can be `null`, so handle that check.
  • The input format `[[7, null], [13, 0]]` means node 0 has value 7 and random points to null; node 1 has value 13 and random points to node 0.

Related Problems

← All problems