Copy List with Random Pointer

🎯

Copy List with Random Pointer

mediumDESIGNAmazonMicrosoftGoogle

Imagine you have a complex linked list where each node not only points to the next node but also to any random node in the list. You want to create a completely independent copy of this structure without mixing the original and the copy.

💡 This problem is about creating a deep copy of a complex linked list where each node has an additional random pointer. Beginners often struggle because the random pointers can point anywhere, making a simple traversal insufficient. Understanding how to preserve these arbitrary connections is key.

📋

Problem Statement

Given a linked list where each node contains an additional random pointer which could point to any node in the list or null, return a deep copy of the list. The deep copy should have exactly the same structure and values, but all nodes should be new instances.

1 ≤ n ≤ 10^5Node values can be any integerRandom pointer can be null or point to any node in the list

💡

Example

Input"head = [[7,null],[13,0],[11,4],[10,2],[1,0]]"

Output[[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.

• Empty list → return null
• List with one node, random pointer points to itself → copy should replicate this
• Random pointers all null → copy should have all random pointers null
• Random pointers forming cycles → copy should replicate cycles without infinite loops

⚠️

Common Mistakes

Not handling null random pointers

Leads to null pointer exceptions or incorrect assignments

✅ Always check if random pointer is null before accessing

Mixing original and copied nodes after weaving

Original list structure is corrupted or copied list is incorrect

✅ Carefully restore original list's next pointers when separating lists

Not using memoization in recursive approach

Infinite recursion or duplicate nodes created

✅ Use a map to cache copied nodes and avoid repeated work

Returning original head instead of copied head

Output is the original list, not the copy

✅ Return the copied head node stored or created during copying

🧠

Brute Force (Using Hash Map for Node Mapping)

💡 This approach uses extra space to map original nodes to their copies. It is straightforward and helps beginners understand the problem by separating node creation and pointer assignment.

Intuition

Create a new node for each original node and store the mapping. Then assign next and random pointers for the copied nodes using this map.

Algorithm

1. Traverse the original list and create a copy of each node, storing the mapping from original to copy in a hash map.
2. Traverse the original list again to assign next and random pointers for each copied node using the hash map.
3. Return the copied node corresponding to the original head.

💡 Separating node creation and pointer assignment makes it easier to understand and debug.

</>

Code

class Node:
    def __init__(self, val, next=None, random=None):
        self.val = val
        self.next = next
        self.random = random

def copyRandomList(head):
    if not head:
        return None
    old_to_new = {}
    curr = head
    while curr:
        old_to_new[curr] = Node(curr.val)
        curr = curr.next
    curr = head
    while curr:
        old_to_new[curr].next = old_to_new.get(curr.next)
        old_to_new[curr].random = old_to_new.get(curr.random)
        curr = curr.next
    return old_to_new[head]

# Driver code to test
if __name__ == '__main__':
    # Create list: 7->13->11->10->1 with random pointers
    nodes = [Node(7), Node(13), Node(11), Node(10), Node(1)]
    nodes[0].next = nodes[1]
    nodes[1].next = nodes[2]
    nodes[2].next = nodes[3]
    nodes[3].next = nodes[4]
    nodes[1].random = nodes[0]
    nodes[2].random = nodes[4]
    nodes[3].random = nodes[2]
    nodes[4].random = nodes[0]
    copied_head = copyRandomList(nodes[0])
    print(copied_head.val)  # Should print 7

Line Notes

class Node:Defines the node structure with val, next, and random pointers

old_to_new = {}Creates a dictionary to map original nodes to their copies

while curr:First pass to create all new nodes without setting pointers

old_to_new[curr] = Node(curr.val)Creates a new node for each original node

old_to_new[curr].next = old_to_new.get(curr.next)Assigns the next pointer for the copied node using the map

old_to_new[curr].random = old_to_new.get(curr.random)Assigns the random pointer for the copied node using the map

return old_to_new[head]Returns the head of the copied list

import java.util.HashMap;
class Node {
    int val;
    Node next;
    Node random;
    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
public class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) return null;
        HashMap<Node, Node> map = new HashMap<>();
        Node curr = head;
        while (curr != null) {
            map.put(curr, new Node(curr.val));
            curr = curr.next;
        }
        curr = head;
        while (curr != null) {
            map.get(curr).next = map.get(curr.next);
            map.get(curr).random = map.get(curr.random);
            curr = curr.next;
        }
        return map.get(head);
    }

    // Driver code
    public static void main(String[] args) {
        Node[] nodes = new Node[5];
        nodes[0] = new Node(7);
        nodes[1] = new Node(13);
        nodes[2] = new Node(11);
        nodes[3] = new Node(10);
        nodes[4] = new Node(1);
        nodes[0].next = nodes[1];
        nodes[1].next = nodes[2];
        nodes[2].next = nodes[3];
        nodes[3].next = nodes[4];
        nodes[1].random = nodes[0];
        nodes[2].random = nodes[4];
        nodes[3].random = nodes[2];
        nodes[4].random = nodes[0];
        Solution sol = new Solution();
        Node copiedHead = sol.copyRandomList(nodes[0]);
        System.out.println(copiedHead.val); // Should print 7
    }
}

Line Notes

import java.util.HashMap;Imports HashMap for mapping original to copied nodes

HashMap<Node, Node> map = new HashMap<>();Stores mapping from original to copied nodes

while (curr != null)First pass to create new nodes

map.put(curr, new Node(curr.val));Creates a copy of the current node

map.get(curr).next = map.get(curr.next);Assigns next pointer for copied node

map.get(curr).random = map.get(curr.random);Assigns random pointer for copied node

return map.get(head);Returns the copied list's head

#include <iostream>
#include <unordered_map>
using namespace std;

class Node {
public:
    int val;
    Node* next;
    Node* random;
    Node(int _val) {
        val = _val;
        next = nullptr;
        random = nullptr;
    }
};

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (!head) return nullptr;
        unordered_map<Node*, Node*> map;
        Node* curr = head;
        while (curr) {
            map[curr] = new Node(curr->val);
            curr = curr->next;
        }
        curr = head;
        while (curr) {
            map[curr]->next = map[curr->next];
            map[curr]->random = map[curr->random];
            curr = curr->next;
        }
        return map[head];
    }
};

// Driver code
int main() {
    Node* nodes[5] = {new Node(7), new Node(13), new Node(11), new Node(10), new Node(1)};
    nodes[0]->next = nodes[1];
    nodes[1]->next = nodes[2];
    nodes[2]->next = nodes[3];
    nodes[3]->next = nodes[4];
    nodes[1]->random = nodes[0];
    nodes[2]->random = nodes[4];
    nodes[3]->random = nodes[2];
    nodes[4]->random = nodes[0];
    Solution sol;
    Node* copiedHead = sol.copyRandomList(nodes[0]);
    cout << copiedHead->val << endl; // Should print 7
    return 0;
}

Line Notes

#include <unordered_map>Includes unordered_map for mapping original to copied nodes

unordered_map<Node*, Node*> map;Maps original nodes to their copies

while (curr) {First pass to create new nodes

map[curr] = new Node(curr->val);Creates a new node copy

map[curr]->next = map[curr->next];Assigns next pointer for copied node

map[curr]->random = map[curr->random];Assigns random pointer for copied node

return map[head];Returns the head of the copied list

function Node(val, next = null, random = null) {
    this.val = val;
    this.next = next;
    this.random = random;
}

var copyRandomList = function(head) {
    if (!head) return null;
    const map = new Map();
    let curr = head;
    while (curr) {
        map.set(curr, new Node(curr.val));
        curr = curr.next;
    }
    curr = head;
    while (curr) {
        map.get(curr).next = map.get(curr.next) || null;
        map.get(curr).random = map.get(curr.random) || null;
        curr = curr.next;
    }
    return map.get(head);
};

// Driver code
const nodes = [new Node(7), new Node(13), new Node(11), new Node(10), new Node(1)];
nodes[0].next = nodes[1];
nodes[1].next = nodes[2];
nodes[2].next = nodes[3];
nodes[3].next = nodes[4];
nodes[1].random = nodes[0];
nodes[2].random = nodes[4];
nodes[3].random = nodes[2];
nodes[4].random = nodes[0];
const copiedHead = copyRandomList(nodes[0]);
console.log(copiedHead.val); // Should print 7

Line Notes

function Node(val, next = null, random = null) {Defines the node structure with val, next, and random pointers

const map = new Map();Stores mapping from original nodes to copied nodes

while (curr) {First pass to create copies of nodes

map.set(curr, new Node(curr.val));Creates a new node copy

map.get(curr).next = map.get(curr.next) || null;Assigns next pointer for copied node

map.get(curr).random = map.get(curr.random) || null;Assigns random pointer for copied node

return map.get(head);Returns the copied list's head

⏱

Complexity

TimeO(n)

SpaceO(n)

We traverse the list twice, each O(n). The hash map stores n nodes, so O(n) space.

💡 For n=100,000 nodes, this means about 200,000 operations plus memory for 100,000 node mappings.

Interview Verdict: Accepted

This approach is accepted but uses extra space. It is a good starting point to understand the problem.

🧠

Optimal Approach (Weaving Nodes Without Extra Hash Map)

💡 This approach cleverly weaves copied nodes into the original list to avoid extra space. It is more complex but optimal in space, teaching how to manipulate pointers carefully.

Intuition

Insert copied nodes right after original nodes, then assign random pointers by using the next pointers, and finally separate the two lists.

Algorithm

1. Traverse the original list and insert a copied node after each original node.
2. Traverse the new list and assign random pointers for copied nodes using original nodes' random pointers.
3. Separate the original and copied nodes to form two independent lists.
4. Return the head of the copied list.

💡 This approach requires careful pointer manipulation but saves space by avoiding a hash map.

</>

Code

class Node:
    def __init__(self, val, next=None, random=None):
        self.val = val
        self.next = next
        self.random = random

def copyRandomList(head):
    if not head:
        return None
    curr = head
    # Step 1: Insert copied nodes
    while curr:
        new_node = Node(curr.val, curr.next)
        curr.next = new_node
        curr = new_node.next
    # Step 2: Assign random pointers
    curr = head
    while curr:
        if curr.random:
            curr.next.random = curr.random.next
        curr = curr.next.next
    # Step 3: Separate lists
    curr = head
    copy_head = head.next
    copy_curr = copy_head
    while curr:
        curr.next = curr.next.next
        if copy_curr.next:
            copy_curr.next = copy_curr.next.next
        curr = curr.next
        copy_curr = copy_curr.next
    return copy_head

# Driver code
if __name__ == '__main__':
    nodes = [Node(7), Node(13), Node(11), Node(10), Node(1)]
    nodes[0].next = nodes[1]
    nodes[1].next = nodes[2]
    nodes[2].next = nodes[3]
    nodes[3].next = nodes[4]
    nodes[1].random = nodes[0]
    nodes[2].random = nodes[4]
    nodes[3].random = nodes[2]
    nodes[4].random = nodes[0]
    copied_head = copyRandomList(nodes[0])
    print(copied_head.val)  # Should print 7

Line Notes

while curr:First pass to weave copied nodes after originals

new_node = Node(curr.val, curr.next)Creates a copy node pointing to original's next

curr.next = new_nodeInserts copy node after original

if curr.random:Assigns random pointer for copied node using original's random

curr.next.random = curr.random.nextCopied node's random points to copied random node

curr.next = curr.next.nextRestores original list's next pointers during separation

copy_curr.next = copy_curr.next.nextBuilds copied list's next pointers during separation

class Node {
    int val;
    Node next;
    Node random;
    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
public class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) return null;
        Node curr = head;
        // Step 1: Insert copied nodes
        while (curr != null) {
            Node newNode = new Node(curr.val);
            newNode.next = curr.next;
            curr.next = newNode;
            curr = newNode.next;
        }
        // Step 2: Assign random pointers
        curr = head;
        while (curr != null) {
            if (curr.random != null) {
                curr.next.random = curr.random.next;
            }
            curr = curr.next.next;
        }
        // Step 3: Separate lists
        curr = head;
        Node copyHead = head.next;
        Node copyCurr = copyHead;
        while (curr != null) {
            curr.next = curr.next.next;
            if (copyCurr.next != null) {
                copyCurr.next = copyCurr.next.next;
            }
            curr = curr.next;
            copyCurr = copyCurr.next;
        }
        return copyHead;
    }

    // Driver code
    public static void main(String[] args) {
        Node[] nodes = new Node[5];
        nodes[0] = new Node(7);
        nodes[1] = new Node(13);
        nodes[2] = new Node(11);
        nodes[3] = new Node(10);
        nodes[4] = new Node(1);
        nodes[0].next = nodes[1];
        nodes[1].next = nodes[2];
        nodes[2].next = nodes[3];
        nodes[3].next = nodes[4];
        nodes[1].random = nodes[0];
        nodes[2].random = nodes[4];
        nodes[3].random = nodes[2];
        nodes[4].random = nodes[0];
        Solution sol = new Solution();
        Node copiedHead = sol.copyRandomList(nodes[0]);
        System.out.println(copiedHead.val); // Should print 7
    }
}

Line Notes

while (curr != null)First pass to weave copied nodes after originals

Node newNode = new Node(curr.val);Creates a copy node

curr.next = newNode;Inserts copy node after original

if (curr.random != null)Assigns random pointer for copied node

curr.next.random = curr.random.next;Copied node's random points to copied random node

curr.next = curr.next.next;Restores original list's next pointers during separation

copyCurr.next = copyCurr.next.next;Builds copied list's next pointers during separation

#include <iostream>
using namespace std;

class Node {
public:
    int val;
    Node* next;
    Node* random;
    Node(int _val) {
        val = _val;
        next = nullptr;
        random = nullptr;
    }
};

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (!head) return nullptr;
        Node* curr = head;
        // Step 1: Insert copied nodes
        while (curr) {
            Node* newNode = new Node(curr->val);
            newNode->next = curr->next;
            curr->next = newNode;
            curr = newNode->next;
        }
        // Step 2: Assign random pointers
        curr = head;
        while (curr) {
            if (curr->random) {
                curr->next->random = curr->random->next;
            }
            curr = curr->next->next;
        }
        // Step 3: Separate lists
        curr = head;
        Node* copyHead = head->next;
        Node* copyCurr = copyHead;
        while (curr) {
            curr->next = curr->next->next;
            if (copyCurr->next) {
                copyCurr->next = copyCurr->next->next;
            }
            curr = curr->next;
            copyCurr = copyCurr->next;
        }
        return copyHead;
    }
};

// Driver code
int main() {
    Node* nodes[5] = {new Node(7), new Node(13), new Node(11), new Node(10), new Node(1)};
    nodes[0]->next = nodes[1];
    nodes[1]->next = nodes[2];
    nodes[2]->next = nodes[3];
    nodes[3]->next = nodes[4];
    nodes[1]->random = nodes[0];
    nodes[2]->random = nodes[4];
    nodes[3]->random = nodes[2];
    nodes[4]->random = nodes[0];
    Solution sol;
    Node* copiedHead = sol.copyRandomList(nodes[0]);
    cout << copiedHead->val << endl; // Should print 7
    return 0;
}

Line Notes

while (curr) {First pass to weave copied nodes after originals

Node* newNode = new Node(curr->val);Creates a copy node

curr->next = newNode;Inserts copy node after original

if (curr->random) {Assigns random pointer for copied node

curr->next->random = curr->random->next;Copied node's random points to copied random node

curr->next = curr->next->next;Restores original list's next pointers during separation

copyCurr->next = copyCurr->next->next;Builds copied list's next pointers during separation

function Node(val, next = null, random = null) {
    this.val = val;
    this.next = next;
    this.random = random;
}

var copyRandomList = function(head) {
    if (!head) return null;
    let curr = head;
    // Step 1: Insert copied nodes
    while (curr) {
        let newNode = new Node(curr.val, curr.next);
        curr.next = newNode;
        curr = newNode.next;
    }
    // Step 2: Assign random pointers
    curr = head;
    while (curr) {
        if (curr.random) {
            curr.next.random = curr.random.next;
        }
        curr = curr.next.next;
    }
    // Step 3: Separate lists
    curr = head;
    let copyHead = head.next;
    let copyCurr = copyHead;
    while (curr) {
        curr.next = curr.next.next;
        if (copyCurr.next) {
            copyCurr.next = copyCurr.next.next;
        }
        curr = curr.next;
        copyCurr = copyCurr.next;
    }
    return copyHead;
};

// Driver code
const nodes = [new Node(7), new Node(13), new Node(11), new Node(10), new Node(1)];
nodes[0].next = nodes[1];
nodes[1].next = nodes[2];
nodes[2].next = nodes[3];
nodes[3].next = nodes[4];
nodes[1].random = nodes[0];
nodes[2].random = nodes[4];
nodes[3].random = nodes[2];
nodes[4].random = nodes[0];
const copiedHead = copyRandomList(nodes[0]);
console.log(copiedHead.val); // Should print 7

Line Notes

while (curr) {First pass to weave copied nodes after originals

let newNode = new Node(curr.val, curr.next);Creates a copy node

curr.next = newNode;Inserts copy node after original

if (curr.random) {Assigns random pointer for copied node

curr.next.random = curr.random.next;Copied node's random points to copied random node

curr.next = curr.next.next;Restores original list's next pointers during separation

copyCurr.next = copyCurr.next.next;Builds copied list's next pointers during separation

⏱

Complexity

TimeO(n)

SpaceO(1)

We traverse the list three times, each O(n). No extra hash map is used, so space is O(1).

💡 For n=100,000 nodes, this means about 300,000 operations but minimal extra memory usage.

Interview Verdict: Accepted

This is the optimal approach in terms of space and is preferred in interviews once you understand the problem.

🧠

Recursive Approach with Memoization

💡 This approach uses recursion and a hash map to avoid repeated copying of nodes. It helps understand the problem from a top-down perspective and recursion practice.

Intuition

Recursively copy each node and its next and random pointers, using a map to avoid infinite recursion and duplicate copies.

Algorithm

1. If the current node is null, return null.
2. If the current node is already copied (in map), return the copy.
3. Create a copy of the current node and store it in the map.
4. Recursively copy the next and random pointers and assign them to the copied node.
5. Return the copied node.

💡 Memoization prevents infinite recursion and duplicate nodes by caching copies.

</>

Code

class Node:
    def __init__(self, val, next=None, random=None):
        self.val = val
        self.next = next
        self.random = random

def copyRandomList(head):
    old_to_new = {}
    def dfs(node):
        if not node:
            return None
        if node in old_to_new:
            return old_to_new[node]
        copy = Node(node.val)
        old_to_new[node] = copy
        copy.next = dfs(node.next)
        copy.random = dfs(node.random)
        return copy
    return dfs(head)

# Driver code
if __name__ == '__main__':
    nodes = [Node(7), Node(13), Node(11), Node(10), Node(1)]
    nodes[0].next = nodes[1]
    nodes[1].next = nodes[2]
    nodes[2].next = nodes[3]
    nodes[3].next = nodes[4]
    nodes[1].random = nodes[0]
    nodes[2].random = nodes[4]
    nodes[3].random = nodes[2]
    nodes[4].random = nodes[0]
    copied_head = copyRandomList(nodes[0])
    print(copied_head.val)  # Should print 7

Line Notes

old_to_new = {}Memoization dictionary to avoid duplicate copies

def dfs(node):Recursive function to copy nodes

if not node:Base case: null node returns null

if node in old_to_new:Return already copied node to prevent duplicates

copy = Node(node.val)Create a copy of the current node

old_to_new[node] = copyStore copy in memoization map

copy.next = dfs(node.next)Recursively copy next pointer

copy.random = dfs(node.random)Recursively copy random pointer

return copyReturn the copied node

import java.util.HashMap;
class Node {
    int val;
    Node next;
    Node random;
    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
public class Solution {
    private HashMap<Node, Node> map = new HashMap<>();
    public Node copyRandomList(Node head) {
        if (head == null) return null;
        if (map.containsKey(head)) return map.get(head);
        Node copy = new Node(head.val);
        map.put(head, copy);
        copy.next = copyRandomList(head.next);
        copy.random = copyRandomList(head.random);
        return copy;
    }

    // Driver code
    public static void main(String[] args) {
        Node[] nodes = new Node[5];
        nodes[0] = new Node(7);
        nodes[1] = new Node(13);
        nodes[2] = new Node(11);
        nodes[3] = new Node(10);
        nodes[4] = new Node(1);
        nodes[0].next = nodes[1];
        nodes[1].next = nodes[2];
        nodes[2].next = nodes[3];
        nodes[3].next = nodes[4];
        nodes[1].random = nodes[0];
        nodes[2].random = nodes[4];
        nodes[3].random = nodes[2];
        nodes[4].random = nodes[0];
        Solution sol = new Solution();
        Node copiedHead = sol.copyRandomList(nodes[0]);
        System.out.println(copiedHead.val); // Should print 7
    }
}

Line Notes

import java.util.HashMap;Imports HashMap for memoization

private HashMap<Node, Node> map = new HashMap<>();Memoization map to avoid duplicate copies

if (map.containsKey(head)) return map.get(head);Return cached copy if exists

Node copy = new Node(head.val);Create copy node

map.put(head, copy);Store copy in map

copy.next = copyRandomList(head.next);Recursively copy next pointer

copy.random = copyRandomList(head.random);Recursively copy random pointer

return copy;Return the copied node

#include <iostream>
#include <unordered_map>
using namespace std;

class Node {
public:
    int val;
    Node* next;
    Node* random;
    Node(int _val) {
        val = _val;
        next = nullptr;
        random = nullptr;
    }
};

class Solution {
public:
    unordered_map<Node*, Node*> map;
    Node* copyRandomList(Node* head) {
        if (!head) return nullptr;
        if (map.count(head)) return map[head];
        Node* copy = new Node(head->val);
        map[head] = copy;
        copy->next = copyRandomList(head->next);
        copy->random = copyRandomList(head->random);
        return copy;
    }
};

// Driver code
int main() {
    Node* nodes[5] = {new Node(7), new Node(13), new Node(11), new Node(10), new Node(1)};
    nodes[0]->next = nodes[1];
    nodes[1]->next = nodes[2];
    nodes[2]->next = nodes[3];
    nodes[3]->next = nodes[4];
    nodes[1]->random = nodes[0];
    nodes[2]->random = nodes[4];
    nodes[3]->random = nodes[2];
    nodes[4]->random = nodes[0];
    Solution sol;
    Node* copiedHead = sol.copyRandomList(nodes[0]);
    cout << copiedHead->val << endl; // Should print 7
    return 0;
}

Line Notes

#include <unordered_map>Includes unordered_map for memoization

unordered_map<Node*, Node*> map;Memoization map to avoid duplicate copies

if (map.count(head)) return map[head];Return cached copy if exists

Node* copy = new Node(head->val);Create copy node

map[head] = copy;Store copy in map

copy->next = copyRandomList(head->next);Recursively copy next pointer

copy->random = copyRandomList(head->random);Recursively copy random pointer

return copy;Return the copied node

function Node(val, next = null, random = null) {
    this.val = val;
    this.next = next;
    this.random = random;
}

var copyRandomList = function(head) {
    const map = new Map();
    function dfs(node) {
        if (!node) return null;
        if (map.has(node)) return map.get(node);
        const copy = new Node(node.val);
        map.set(node, copy);
        copy.next = dfs(node.next);
        copy.random = dfs(node.random);
        return copy;
    }
    return dfs(head);
};

// Driver code
const nodes = [new Node(7), new Node(13), new Node(11), new Node(10), new Node(1)];
nodes[0].next = nodes[1];
nodes[1].next = nodes[2];
nodes[2].next = nodes[3];
nodes[3].next = nodes[4];
nodes[1].random = nodes[0];
nodes[2].random = nodes[4];
nodes[3].random = nodes[2];
nodes[4].random = nodes[0];
const copiedHead = copyRandomList(nodes[0]);
console.log(copiedHead.val); // Should print 7

Line Notes

const map = new Map();Memoization map to avoid duplicate copies

function dfs(node) {Recursive function to copy nodes

if (!node) return null;Base case: null node returns null

if (map.has(node)) return map.get(node);Return cached copy if exists

const copy = new Node(node.val);Create copy node

map.set(node, copy);Store copy in map

copy.next = dfs(node.next);Recursively copy next pointer

copy.random = dfs(node.random);Recursively copy random pointer

return copy;Return the copied node

⏱

Complexity

TimeO(n)

SpaceO(n)

Each node is copied once, but recursion stack and map use O(n) space.

💡 For n=100,000 nodes, recursion depth and map size can be large, so watch for stack overflow.

Interview Verdict: Accepted

This approach is elegant and accepted but may risk stack overflow on very large lists.

📊

All Approaches - One-Glance Tradeoffs

💡 The hash map approach is easiest to implement and understand, but uses extra space. The weaving approach is optimal in space but more complex. Recursive memoization is elegant but risks stack overflow.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Hash Map)	O(n)	O(n)	No	Yes	Good to mention and implement if allowed extra space
2. Optimal (Weaving Nodes)	O(n)	O(1)	No	Yes	Preferred approach to code in interviews for optimal space
3. Recursive with Memoization	O(n)	O(n)	Yes (deep recursion)	Yes	Good to mention; implement if recursion is preferred

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before your interview. Start with the brute force approach to build intuition, then learn the optimal weaving technique. Practice coding and explaining each step clearly.

How to Present

Clarify the problem and ask about constraints.Explain the brute force approach using a hash map for clarity.Discuss the space-optimized weaving approach as the optimal solution.Mention the recursive memoization approach if recursion is preferred.Write clean code and test edge cases.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 10min → Test: 5min. Total ~23min

What the Interviewer Tests

The interviewer tests your understanding of deep copy, pointer manipulation, and handling arbitrary random pointers without mixing original and copied nodes.

Common Follow-ups

• What if random pointers can form cycles? → Your approach handles cycles naturally with memoization or weaving.
• Can you do it without extra space? → Yes, the weaving approach achieves O(1) space.

💡 These follow-ups test your grasp of edge cases and space optimization, common in interviews.

🔍

Pattern Recognition

When to Use

1) You need to copy a complex linked structure, 2) Nodes have arbitrary pointers, 3) Deep copy is required, 4) Avoid mixing original and copy nodes.

Signature Phrases

random pointerdeep copycopy list with arbitrary pointer

NOT This Pattern When

Shallow copy problems or simple linked list copy without random pointers

Similar Problems

Clone Graph - similar deep copy with arbitrary connectionsCopy Binary Tree with Random Pointer - tree variant of this problem

Practice

1. You need to design a stack data structure that supports the usual push and pop operations, but also an increment operation that adds a given value to the bottom k elements of the stack efficiently. Which approach guarantees the most optimal time complexity for a sequence of n operations?

easy

A. Use a balanced binary search tree to store elements and increments, allowing O(log n) updates and queries.

B. Directly increment the bottom k elements on each increment call, resulting in O(n*k) time for n operations.

C. Use a lazy increment array to record increments and propagate them during pop operations, achieving O(n) total time.

D. Maintain a prefix sum array of increments and update it on each increment call, applying increments during pop.

Solution

1. Step 1: Understand the problem constraints

   The increment operation must be efficient even when called multiple times, so directly incrementing bottom k elements each time (O(n*k)) is too slow.

2. Step 2: Recognize the lazy increment pattern

   Using an auxiliary array to store increments lazily and applying them during pop operations reduces total time to O(n), as increments are propagated only once per element.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Lazy increments avoid repeated updates, achieving O(n) total time [OK]

Hint: Lazy increments reduce repeated updates to O(n) total time [OK]

Common Mistakes:

• Directly incrementing elements each time causes TLE
• Using complex data structures unnecessarily

2. You need to design a data structure that supports setting values at indices, taking snapshots of the entire array state, and retrieving values at any snapshot efficiently. Which approach best balances time and space complexity for frequent set and get operations?

easy

A. Store full copies of the array on every snapshot to allow O(1) get operations.

B. Maintain a hash map per index storing (snap_id, value) pairs and use binary search to retrieve values for get operations.

C. Use a single global hash map keyed by (index, snap_id) and perform linear search for get operations.

D. Use a segment tree to store snapshots and query values at any snapshot.

Solution

1. Step 1: Understand problem requirements

   The data structure must efficiently support set, snap, and get operations with many snapshots and updates.

2. Step 2: Evaluate approaches

   Storing full snapshots (B) uses too much space and is slow for many snaps. A global hash map with linear search (C) makes get operations slow. Segment trees (D) are complex and not optimal here. Using a hash map per index with binary search (A) allows O(1) amortized set and snap, and O(log m) get, balancing time and space efficiently.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Binary search per index enables fast retrieval [OK]

Hint: Binary search per index enables fast retrieval [OK]

Common Mistakes:

• Thinking full snapshots are efficient for many snaps
• Using linear search for get causes slow queries

3. What is the time complexity of retrieving the news feed for a user in the optimal Twitter design, where k is the number of tweets retrieved (usually 10) and F is the number of followees plus one (the user themselves)?

medium

A. O(F * T log (F * T)) where T is average tweets per user

B. O(F + k log F)

C. O(k log F)

D. O(k * F)

Solution

1. Step 1: Identify operations in getNewsFeed

   We push the head tweet of each followee (F users) into a max heap, then pop up to k tweets, pushing next tweets from linked lists.

2. Step 2: Analyze heap operations

   Heap size is at most F, each pop and push is O(log F), repeated k times -> O(k log F).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Heap operations dominate, linear scans avoided [OK]

Hint: Heap operations depend on followees count, not total tweets [OK]

Common Mistakes:

• Confusing total tweets T with followees F
• Assuming linear scan over all tweets

4. Consider the following buggy code snippet for flattening a multilevel doubly linked list. Which line contains the subtle bug that can cause infinite loops or incorrect list structure?

medium

A. Missing line that sets curr.child to None after splicing

B. Line where tail is found by while tail.next:

C. Line where curr.next is set to child

D. Line where tail.next is connected to curr.next

Solution

1. Step 1: Identify the role of curr.child

   After splicing the child list, curr.child must be set to None to avoid revisiting the child.

2. Step 2: Recognize missing pointer update

   The code does not set curr.child = None, causing infinite loops or incorrect traversal.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Not clearing child pointer leads to repeated processing [OK]

Hint: Always clear child pointer after splicing [OK]

Common Mistakes:

• Forgetting to clear child pointer after splicing
• Incorrectly updating prev pointers instead

5. Suppose the LFU cache must support a new operation: reuse(key) which resets the frequency of key to 1 without changing its value. Which modification to the optimal LFU cache design correctly supports this operation without breaking O(1) complexity?

hard

A. Simply set the frequency of the key to 1 in the key_val_freq map without moving it between frequency lists

B. Clear the entire cache and reinsert the key with frequency 1

C. Remove the key from its current frequency list and add it to freq=1 list, update min_freq to 1

D. Increment the frequency of the key by 1 and then reset min_freq to 1

Solution

1. Step 1: Understand reuse operation

   Reuse resets frequency to 1, so the key must move from its current frequency list to the freq=1 list.

2. Step 2: Update data structures accordingly

   Remove key from old freq list, add to freq=1 list, and update min_freq to 1 to reflect the new minimum frequency.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Moving key between freq lists and updating min_freq preserves O(1) operations [OK]

Hint: Move key to freq=1 list and update min_freq [OK]

Common Mistakes:

• Not moving key between frequency lists
• Resetting frequency without updating min_freq
• Clearing cache is inefficient and breaks O(1)