DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Copy List with Random Pointer

mediumLinked listAmazon SysDE

Problem statement

Each node of a singly linked list has a value, a next pointer, and an extra random pointer that can point to any node in the same list, or to null.

Make a deep copy of the list: a brand-new set of nodes with the same values, where each copy's next and random point to the corresponding copies, never to nodes of the original list. Return the head of the copy. The original list must be left as it was.

In the examples, each node is written as (value, random), where random is the index of the node it points to.

Examples

Example 1

Input: [(4, 2), (9, 0), (1, null)]

Output: [(4, 2), (9, 0), (1, null)] built from three new nodes

Explanation: The copy of node 0 must point randomly to the copy of node 2, not to the original node 2.

Example 2

Input: [(5, 0), (5, 1)]

Output: [(5, 0), (5, 1)] built from two new nodes

Explanation: Each node's random points to itself. Values repeat, so you cannot match nodes up by value.

Hints

Approach

Use the list itself as the map by weaving the copies in.

  1. Interleave. After each original node A, insert its copy A': A -> A' -> B -> B' -> ....
  2. Random pointers. For each original A, its copy is A.next, and the copy of A.random is A.random.next. So set A.next.random = A.random.next when A.random is not null.
  3. Unweave. Walk the combined list, pointing each original back at the next original and each copy at the next copy. This restores the input and separates out the copy.

No extra data structure is needed beyond the new nodes themselves.

ComplexityTime O(n)Space O(1) extra (besides the copied nodes)
Python
# class Node:
# def __init__(self, x, next=None, random=None):
# self.val = x
# self.next = next
# self.random = random
class Solution:
def copyRandomList(self, head: Node | None) -> Node | None:
if not head:
return None
# 1. insert each copy right after its original: A -> A' -> B -> B' ...
node = head
while node:
node.next = Node(node.val, node.next)
node = node.next.next
# 2. a copy's random is the node right after the original's random
node = head
while node:
if node.random:
node.next.random = node.random.next
node = node.next.next
# 3. split the two lists apart, restoring the original
new_head = head.next
node = head
while node:
copy = node.next
node.next = copy.next
copy.next = copy.next.next if copy.next else None
node = node.next
return new_head

Follow-up questions

  • Deep-copy a general graph where each node has a list of neighbours (Clone Graph).
  • What changes if random can point to a node in a different list?

Frequently asked questions

The node random points to may be later in the list, so its copy has not been created yet. Both approaches solve this by creating all copies before wiring any random pointer.

Yes. The task says the input must be unchanged, and a caller that still holds the original would otherwise find copies spliced into it. The third pass restores every original next pointer.

Cloning anything with internal references, such as a dependency graph of services, a set of resources that refer to each other, or an object graph you are about to mutate for a dry run, has the same problem: references must point into the new copy, not back into the original. The original-to-copy map is how those clone operations stay correct.