Interview Prepcustom-data-structuresmediumAmazonMicrosoftGoogleFacebook

Copy List with Random Pointer

Choose your preparation mode3 modes available

Try It Solution Trace

</>

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.