Bird
Raised Fist0
Interview Prepcustom-data-structuresmediumAmazonMicrosoftGoogleFacebook

Copy List with Random Pointer

Choose your preparation mode4 modes available
🎯
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.
ApproachTimeSpaceStack RiskReconstructUse In Interview
1. Brute Force (Hash Map)O(n)O(n)NoYesGood to mention and implement if allowed extra space
2. Optimal (Weaving Nodes)O(n)O(1)NoYesPreferred approach to code in interviews for optimal space
3. Recursive with MemoizationO(n)O(n)Yes (deep recursion)YesGood 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/5)
1. You are given a singly linked list where each node contains a binary digit (0 or 1). The linked list represents a binary number with the head as the most significant bit. Which approach guarantees an optimal solution to convert this linked list to its decimal integer value?
easy
A. Iteratively accumulate the decimal value by shifting the current value left by 1 and OR-ing with the current node's bit.
B. Use a greedy approach to pick bits that maximize the decimal value at each step.
C. Traverse the list to build a string of bits, then parse the string as a binary number.
D. Apply dynamic programming to store intermediate decimal values for sublists.

Solution

  1. Step 1: Understand the problem constraints

    The linked list represents a binary number with the head as the most significant bit, so the decimal value can be built by processing bits from left to right.
  2. Step 2: Identify the optimal approach

    Iteratively shifting the accumulated value left by 1 and OR-ing with the current bit correctly builds the decimal value in O(n) time and O(1) space, without extra string conversions or complex DP.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Bitwise accumulation matches binary to decimal conversion [OK]
Hint: Bitwise accumulation is optimal for binary to decimal conversion [OK]
Common Mistakes:
  • Using string concatenation then parsing wastes time and space
  • Greedy approaches don't apply to binary number conversion
  • Dynamic programming is unnecessary overhead here
2. You are given a singly linked list and asked to reorder it so that all nodes at odd indices appear before nodes at even indices, preserving the relative order within each group. Which approach guarantees an optimal solution with O(n) time and O(1) space complexity?
easy
A. Using a stack to push odd nodes and then pop them to reorder the list
B. Sorting the list based on node values and then merging odd and even indexed nodes
C. Using two pointers to rearrange nodes in-place by linking odd and even nodes separately and then concatenating
D. Using a hash map to store nodes by index parity and reconstructing the list from the map

Solution

  1. Step 1: Understand problem constraints

    The problem requires reordering nodes by their position (odd/even indices) without extra space and in linear time.
  2. Step 2: Evaluate approaches

    Only the two-pointer in-place rearrangement achieves O(n) time and O(1) space by relinking nodes without extra data structures.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Two-pointer approach is standard for odd-even linked list rearrangement [OK]
Hint: Two pointers rearranging nodes in-place is optimal [OK]
Common Mistakes:
  • Thinking sorting or extra data structures are needed
  • Assuming extra space is acceptable for optimal
3. Given the following code for partitioning a linked list around value x = 3, and the input list: 1 -> 4 -> 2 -> 5, what is the final reordered list returned by the function?
easy
A. 1 -> 4 -> 2 -> 5
B. 1 -> 2 -> 4 -> 5
C. 2 -> 1 -> 4 -> 5
D. 4 -> 1 -> 2 -> 5

Solution

  1. Step 1: Trace initial pointers with input 1 -> 4 -> 2 -> 5 and x=3

    Start with dummy -> 1 -> 4 -> 2 -> 5, less_tail and prev at dummy, current at 1.
  2. Step 2: Process nodes

    Node 1 < 3, less_tail.next == current, move less_tail and prev forward. Node 4 >= 3, move prev and current forward. Node 2 < 3, less_tail.next != current, so remove 2 and insert after less_tail. Final list: 1 -> 2 -> 4 -> 5.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Nodes less than 3 appear first in original order, then others [OK]
Hint: Track less_tail and prev carefully to avoid skipping nodes [OK]
Common Mistakes:
  • Swapping values instead of nodes
  • Incorrect pointer updates causing lost nodes
  • Assuming order changes within partitions
4. You are given a singly linked list and need to reorder it so that the nodes are arranged in the sequence: first node, last node, second node, second last node, and so on. Which approach guarantees an optimal solution with O(n) time and O(1) extra space?
easy
A. Store all nodes in an array, then reorder by reassigning next pointers using two pointers from ends.
B. Use a greedy approach by alternating nodes from the start and end without modifying the list structure.
C. Use dynamic programming to store intermediate reorder states and build the final list.
D. Find the middle of the list, reverse the second half, then merge the two halves alternately.

Solution

  1. Step 1: Understand the problem constraints

    The problem requires reordering nodes in a specific pattern without extra space overhead.
  2. Step 2: Evaluate approaches for time and space

    Finding the middle, reversing the second half, and merging achieves O(n) time and O(1) space, unlike storing nodes or DP which use extra space.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Optimal approach uses middle finding and reversing [OK]
Hint: Middle + reverse + merge is classic reorder pattern [OK]
Common Mistakes:
  • Thinking greedy pointer swaps suffice
  • Using extra arrays unnecessarily
  • Confusing DP with linked list reorder
5. You need to split a singly linked list into k parts such that the sizes of the parts differ by at most one, and the order of nodes is preserved. Which approach guarantees an optimal solution with minimal passes over the list and clean code structure?
easy
A. Use a greedy approach that assigns nodes to parts until the next part would be larger, then move on.
B. Split the list by repeatedly removing the head node and appending it to parts until all nodes are distributed.
C. Precompute the total length, then split the list in-place using dummy heads and careful pointer manipulation.
D. Apply dynamic programming to decide the best split points to minimize size differences.

Solution

  1. Step 1: Understand the problem constraints

    The parts must differ in size by at most one, and the original order must be preserved.
  2. Step 2: Evaluate approaches

    Greedy and naive removal approaches do not guarantee minimal passes or clean code. Dynamic programming is unnecessary overhead. Precomputing length and using dummy heads allows a single pass split with clear structure.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Precomputing length and dummy heads -> minimal passes and clean code [OK]
Hint: Precompute length, then split in-place with dummy heads [OK]
Common Mistakes:
  • Assuming greedy splitting always works
  • Using DP unnecessarily
  • Splitting without precomputing length
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard