Interview Prepcustom-data-structuresmediumAmazonMicrosoftGoogleFacebook

Copy List with Random Pointer

Choose your preparation mode4 modes available

Try It Solution Trace

Start learning this pattern below

Jump into concepts and practice - no test required

Recommended

Test this pattern10 questions across easy, medium, and hard to know if this pattern is strong

</>

IDE

def copyRandomList(head: 'Node') -> 'Node':

def copyRandomList(head):
    # Write your solution here
    pass

class Solution {
    public Node copyRandomList(Node head) {
        // Write your solution here
        return null;
    }
}

#include <vector>
using namespace std;

Node* copyRandomList(Node* head) {
    // Write your solution here
    return nullptr;
}

function copyRandomList(head) {
    // Write your solution here
}

0/10

Common Bugs to Avoid

Wrong: Random pointers in copied list point to original nodes instead of copied nodes.Forgot to use a mapping from original to copied nodes when assigning random pointers.✅ Use a dictionary/map to store original->copy node mapping and assign random pointers using this map.

Wrong: Function crashes or returns non-null for empty input.No base case handling for empty input (null head).✅ Add a check at the start: if head is null, return null immediately.

Wrong: Infinite recursion or timeout on inputs with cycles in random pointers.No visited map or memoization to handle cycles in random pointers.✅ Use a map to track visited nodes and avoid revisiting during recursion or iteration.

Wrong: Random pointers in copied list do not preserve shared references, creating multiple copies of the same node.Assigning random pointers without reusing copied nodes from the map.✅ Always assign random pointers using the map to ensure shared references point to the same copied node.

Wrong: Solution times out on large inputs.Using exponential or quadratic time approach instead of O(n).✅ Implement O(n) time solution using hash map or node weaving technique.

✓

Test Cases

t1_01basic

Input{"head":[[7,null],[13,0],[11,4],[10,2],[1,0]]}

Expected[[7,null],[13,0],[11,4],[10,2],[1,0]]

The list has 5 nodes. Each node's random pointer points to the index given (or null). The output is a deep copy with the same structure and random pointers.

t1_02basic

Input{"head":[[1,null],[2,0],[3,1]]}

Expected[[1,null],[2,0],[3,1]]

List of 3 nodes where random pointers form a chain back to previous nodes. The deep copy must replicate this structure exactly.

Practice

(1/5)

1. Consider the following Python code implementing an optimal linked list. After executing these operations: addAtHead(1), addAtTail(3), addAtIndex(1, 2), what is the value returned by get(1)?

easy

A. 2

B. 1

C. 3

D. -1

Copy List with Random Pointer

Start learning this pattern below

Practice

Solution

Step 1: Trace addAtHead(1)

Step 2: Trace addAtTail(3)

Step 3: Trace addAtIndex(1, 2)

Step 4: Trace get(1)

Final Answer:

Quick Check:

Solution

Step 1: Initial state

Step 2: First iteration with child

Final Answer:

Quick Check:

Solution

Step 1: Identify pointer updates

Step 2: Locate missing update

Final Answer:

Quick Check:

Solution

Step 1: Identify complexity of outer and inner loops

Step 2: Check if recursion stack adds extra space

Final Answer:

Quick Check:

Solution

Step 1: Identify missing boundary check

Step 2: Consequence of missing check

Final Answer:

Quick Check: