Pattern visualizer
Copy List with Random Pointer
Cloning next pointers alone is a plain list copy. The random pointer is what makes this hard: it can point at a node anywhere in the list, including one that has not been cloned yet if the scan is only left to right. The array view here shows the original node values; the cur pointer walks the list while the random pointer (when a node has one) marks which index that node's random target lives at. The fix is two passes: first clone every node and store original-to-clone in a hash map, with no wiring yet. Once every node has a clone waiting in the map, a second pass can safely set clone.next and clone.random by looking up map[original.next] and map[original.random] — order no longer matters because every possible target already has a clone. Animated on: A linked list where each node also has a random pointer that can point to any node or null. Values [7, 13, 11, 10], random targets by index [none, 0, 3, 1]. Produce a completely independent deep copy with the same structure..
Hash map dictionary: clone every node, then rewire next/random by lookup
4 nodes with values [7, 13, 11, 10]. Random targets by index: [none, 0, 3, 1] — node 1's random points at node 0, node 2's at node 3. A random pointer can jump anywhere, even forward to a node not cloned yet, so a single left-to-right pass cannot wire it up immediately.
1FUNCTION copyRandomList(head)2 IF head = NULL3 RETURN NULL4 map <- EMPTY MAP5 cur <- head6 WHILE cur != NULL7 map[cur] <- NEW NODE(cur.val)8 cur <- cur.next9 cur <- head10 WHILE cur != NULL11 map[cur].next <- map[cur.next]12 map[cur].random <- map[cur.random]13 cur <- cur.next14 RETURN map[head]
← / → step · space play · Home restart