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 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. Given the following code for odd-even linked list rearrangement, what is the output list after running the function on the input list [1, 2, 3, 4]?

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def oddEvenList(head):
    if not head or not head.next:
        return head
    odd = head
    even = head.next
    even_head = even
    while even and even.next:
        odd.next = even.next
        odd = odd.next
        even.next = odd.next
        even = even.next
    odd.next = even_head
    return head

# Input list: 1 -> 2 -> 3 -> 4
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4))))
new_head = oddEvenList(head)
curr = new_head
res = []
while curr:
    res.append(curr.val)
    curr = curr.next
print(res)

easy

A. [1, 2, 3, 4]

B. [1, 3, 2, 4]

C. [2, 4, 1, 3]

D. [1, 3, 4, 2]

Solution

1. Step 1: Trace first iteration of while loop

   odd=1, even=2, even.next=3; odd.next=3, odd moves to 3; even.next=4, even moves to 4.

2. Step 2: Loop ends as even.next is null; link odd.next to even_head (2)

   Final list order: 1 -> 3 -> 2 -> 4.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Output matches expected odd-even rearrangement for input [1,2,3,4] [OK]

Hint: Odd nodes first, then even nodes in original order [OK]

Common Mistakes:

• Confusing node values with indices
• Off-by-one errors in pointer updates

3. 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

4. Consider the following Python code implementing the recursive reorder list approach. Given the input list 1->2->3, what is the printed output after calling reorderList(n1)?

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reorderList(head):
    def helper(front, back):
        if not back:
            return True
        if not helper(front, back.next):
            return False
        if front[0] == back or front[0].next == back:
            back.next = None
            return False
        tmp = front[0].next
        front[0].next = back
        back.next = tmp
        front[0] = tmp
        return True
    helper([head], head)

n3 = ListNode(3)
n2 = ListNode(2, n3)
n1 = ListNode(1, n2)
reorderList(n1)
curr = n1
while curr:
    print(curr.val, end=' ')
    curr = curr.next

easy

A. 1 3

B. 1 2 3

C. 1 3 2

D. 3 2 1

Solution

1. Step 1: Trace helper calls with input 1->2->3

   Recursion reaches back=null, then unwinds, linking nodes alternately: 1->3->2.

2. Step 2: Verify final list traversal output

   Prints nodes in order: 1 3 2, confirming correct reorder.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Output matches reorder pattern for 3 nodes [OK]

Hint: Small input trace confirms reorder sequence [OK]

Common Mistakes:

• Assuming no reorder happens
• Stopping recursion too early
• Misplacing next pointers

5. Suppose the browser history must support reopening previously visited URLs multiple times without losing forward history (i.e., URLs can be revisited without clearing forward stack). Which modification to the two stacks approach correctly supports this feature?

hard

A. Use a doubly linked list with a current pointer, allowing moving back and forward without clearing forward history on visit.

B. Remove clearing of forward_stack in visit and allow duplicates in back_stack; back and forward remain unchanged.

C. Keep two stacks but add a third stack to track duplicates and manage forward history separately.

D. Use a single list with an index pointer and never slice the list on visit, allowing revisits without losing forward pages.

Solution

1. Step 1: Understand the requirement

   Revisiting URLs should not clear forward history, so forward pages must remain accessible after visit.

2. Step 2: Evaluate data structure modifications

   Two stacks approach relies on clearing forward_stack on visit, so it cannot support this without major changes. A doubly linked list with a current pointer allows moving back and forward freely without clearing forward history.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Doubly linked list supports revisits without losing forward history [OK]

Hint: Doubly linked list allows bidirectional navigation without clearing forward history [OK]

Common Mistakes:

• Removing forward_stack clearing breaks correctness in two stacks
• Adding extra stacks complicates without solving
• Single list without slicing causes stale forward pages