Copy List with Random Pointer

Copy List with Random Pointer

What is this problem about?

The Copy List with Random Pointer interview question is a classic linked list problem. You are given a linked list where each node has a next pointer and an additional random pointer that can point to any node in the list or be null. You must return a deep copy of the entire list. A deep copy means you must create entirely new nodes, and their random pointers must point to the new nodes in the copied list, not the original nodes.

Why is this asked in interviews?

This is one of the most popular Linked List interview patterns, asked by Amazon, Microsoft, and Meta. It tests your ability to handle complex pointer structures and memory mapping. It evaluates whether you can keep track of the relationship between original and copied nodes, typically using a hash map or a clever in-place interleaving technique.

Algorithmic pattern used

There are two main approaches:

1. Hash Table (O(N) space): Traverse the list once to create all new nodes and store them in a map: Map<OriginalNode, CopiedNode>. Traverse again to set the next and random pointers using the map.
2. Interleaving (O(1) space):
   • Create a copy of each node and insert it immediately after the original node (A -> A' -> B -> B').
   • Set the random pointers of the new nodes (A'.random = A.random.next).
   • Separate the two lists.

Example explanation

List: 1 -> 2, where 1.random = 2 and 2.random = 1. Using Hash Table:

1. Map: {1: 1', 2: 2'}.
2. Set pointers for 1': next = 2', random = 2'.
3. Set pointers for 2': next = null, random = 1'. Using Interleaving:
4. 1 -> 1' -> 2 -> 2'.
5. 1'.random = 1.random.next = 2.next = 2'.
6. Separate the lists to get 1' -> 2'.

Common mistakes candidates make

• Shallow Copy: Accidentally pointing the random pointer of a new node back to an original node.
• Null Checks: Forgetting to handle the case where a random pointer is null.
• Original List Integrity: Modifying the original list and not restoring it if using the interleaving method.

Interview preparation tip