Copy List with Random Pointer

Problem Statement

A linked list of length n is given such that each node contains an additional random pointer, which could point to any node in the list, or null.

Construct a deep copy of the list. The deep copy should consist of exactly n brand new nodes, where each new node has its value set to the value of its corresponding original node. Both the next and random pointer of the new nodes should point to new nodes in the copy list such that the pointers in the copy list represent the same relationships as the pointers in the original list (based on the nodes in the original list, not on their values).

Return the head of the copied linked list.

What to notice first

• The difficulty is that you cannot simply traverse and copy — you must also correctly map random pointers to the cloned nodes, not the original ones.
• Nodes can appear in the random pointer chain in any order, so a naive single-pass approach will not work.
• The hash map approach explicitly maps each original node to its clone; the interweaving approach reuses the original list structure temporarily as a mapping.
• Two pointers in different lists are “equivalent” if they point to nodes with the same position in their respective lists.

Examples

Input	Output	Explanation
[[7,null],[13,0],[11,4],[10,2],[1,0]]	Same structure	5-node list; node 13’s random points to node 7 (index 0) in the original, and the copy’s node 13’s random points to the copy’s node 7.
[[1,1],[2,1]]	Same structure	2-node list; both nodes’ random pointers point to node 1 in both original and copy.
[[3,null]]	Same structure	Single node with null random pointer.

Constraints

• 0 <= n <= 100
• -100 <= Node.val <= 100
• Node.random is null or points to some node in the list.

Real-World Applications

Where this pattern appears

• Deep cloning of complex objects — copy an object graph where references can point anywhere, not just linearly.
• Serialization/deserialization — reconstruct a full copy of a graph structure from encoded form.
• Cache replication — duplicate a cached structure with internal cross-references for distributed systems.
• Transaction rollback snapshots — create a snapshot of a linked data structure for recovery purposes.

Complexity Comparison

Approach	Time	Space	Best When
Hash Map	O(n)	O(n)	Most common; easier to understand and implement
Interweaving	O(n)	O(1)	Space is critical; demonstrates clever pointer manipulation

Which approach should you learn first?

• Learn Hash Map first — it is straightforward and widely used in interviews.
• Use Interweaving as an advanced follow-up to show deeper understanding of pointer mechanics.

Clear & Intuitive

Hash Map

O(n) time · O(n) space

Space-Optimal

Interweaving

O(n) time · O(1) space

Approach 1: Hash Map

★ Recommended

Use a hash map to store the mapping between original nodes and their clones. In the first pass, create all cloned nodes and store them in the map. In the second pass, connect the next and random pointers of the cloned nodes by looking up the original pointers in the map.

The key insight is to separate node creation from pointer assignment, allowing us to reference any node’s clone regardless of traversal order.

⏱ Time O(n) Two passes 💾 Space O(n) Hash map stores n nodes

Step-by-step Example

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

Original list: 7 → 13 → 11 → 10 → 1

• Node 7’s random: null
• Node 13’s random: 7 (index 0)
• Node 11’s random: 1 (index 4)
• Node 10’s random: 11 (index 2)
• Node 1’s random: 7 (index 0)

Step	Node	Action
1	Create clones	Create nodes: 7’, 13’, 11’, 10’, 1’ in hash map
2	Node 7 → 13	Copy 7.next=13 → 7’.next=13’
3	Node 7 → null	Copy 7.random=null → 7’.random=null
4	Node 13 → 0	Copy 13.random=nodes[0] → 13’.random=nodeMap[nodes[0]]=7’

Animated walkthrough

How the hash map solution clones nodes and their pointers

Use Next or Autoplay to see nodes created in the map, then each original pointer mapped to a cloned pointer.

Back Autoplay Next Reset

Step 1 of 3

Waiting to begin...

Array state

Memory / lookup state

Pseudocode

function copyRandomList(head):
    if head is null:
        return null

    nodeMap = {}

    // First pass: create all nodes
    current = head
    while current != null:
        nodeMap[current] = Node(current.val)
        current = current.next

    // Second pass: set pointers
    current = head
    while current != null:
        copy = nodeMap[current]
        copy.next = nodeMap[current.next] if current.next else null
        copy.random = nodeMap[current.random] if current.random else null
        current = current.next

    return nodeMap[head]

Solution Code

Python

copy_list_with_random_pointer_hash_map.py

from typing import Optional


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


def copyRandomList(head: Optional[Node]) -> Optional[Node]:
    if not head:
        return None

    # Map original nodes to their copies
    node_map = {}

    # First pass: create all copy nodes
    current = head
    while current:
        node_map[current] = Node(current.val)
        current = current.next

    # Second pass: set next and random pointers
    current = head
    while current:
        copy_node = node_map[current]
        copy_node.next = node_map[current.next] if current.next else None
        copy_node.random = node_map[current.random] if current.random else None
        current = current.next

    return node_map[head]


# Test cases
def print_list(head: Optional[Node]):
    result = []
    current = head
    while current:
        result.append((current.val, current.random.val if current.random else None))
        current = current.next
    return result


# Example 1: [[7,None],[13,0],[11,4],[10,2],[1,0]]
node1 = Node(7)
node2 = Node(13)
node3 = Node(11)
node4 = Node(10)
node5 = Node(1)

node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5

node1.random = None
node2.random = node1
node3.random = node5
node4.random = node3
node5.random = node1

copy = copyRandomList(node1)
print(print_list(copy))  # [(7, None), (13, 7), (11, 1), (10, 11), (1, 7)]

# Example 2: [[1,1],[2,1]]
node6 = Node(1)
node7 = Node(2)
node6.next = node7
node6.random = node6
node7.random = node6

copy2 = copyRandomList(node6)
print(print_list(copy2))  # [(1, 1), (2, 1)]

C++

copy_list_with_random_pointer_hash_map.cpp

#include <unordered_map>
using namespace std;

class Node {
public:
    int val;
    Node* next;
    Node* random;

    Node(int _val) : val(_val), next(NULL), random(NULL) {}
};

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (!head) return NULL;

        // Map original nodes to their copies
        unordered_map<Node*, Node*> nodeMap;

        // First pass: create all copy nodes
        Node* current = head;
        while (current) {
            nodeMap[current] = new Node(current->val);
            current = current->next;
        }

        // Second pass: set next and random pointers
        current = head;
        while (current) {
            Node* copyNode = nodeMap[current];
            copyNode->next = current->next ? nodeMap[current->next] : NULL;
            copyNode->random = current->random ? nodeMap[current->random] : NULL;
            current = current->next;
        }

        return nodeMap[head];
    }
};

Java

copy_list_with_random_pointer_hash_map.java

import java.util.HashMap;
import java.util.Map;

class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}

class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) return null;

        // Map original nodes to their copies
        Map<Node, Node> nodeMap = new HashMap<>();

        // First pass: create all copy nodes
        Node current = head;
        while (current != null) {
            nodeMap.put(current, new Node(current.val));
            current = current.next;
        }

        // Second pass: set next and random pointers
        current = head;
        while (current != null) {
            Node copyNode = nodeMap.get(current);
            copyNode.next = current.next != null ? nodeMap.get(current.next) : null;
            copyNode.random = current.random != null ? nodeMap.get(current.random) : null;
            current = current.next;
        }

        return nodeMap.get(head);
    }
}

JavaScript

copy_list_with_random_pointer_hash_map.js

/**
 * // Definition for a Node.
 * function Node(val, next, random) {
 *    this.val = val;
 *    this.next = next;
 *    this.random = random;
 * };
 */

function copyRandomList(head) {
    if (!head) return null;

    // Map original nodes to their copies
    const nodeMap = new Map();

    // First pass: create all copy nodes
    let current = head;
    while (current) {
        nodeMap.set(current, new Node(current.val));
        current = current.next;
    }

    // Second pass: set next and random pointers
    current = head;
    while (current) {
        const copyNode = nodeMap.get(current);
        copyNode.next = current.next ? nodeMap.get(current.next) : null;
        copyNode.random = current.random ? nodeMap.get(current.random) : null;
        current = current.next;
    }

    return nodeMap.get(head);
}

Rust

copy_list_with_random_pointer_hash_map.rs

use std::cell::RefCell;
use std::collections::HashMap;
use std::rc::Rc;

#[derive(Clone)]
pub struct Node {
    pub val: i32,
    pub next: Option<Rc<RefCell<Node>>>,
    pub random: Option<Rc<RefCell<Node>>>,
}

impl Node {
    pub fn new(val: i32) -> Self {
        Node {
            val,
            next: None,
            random: None,
        }
    }
}

impl Solution {
    pub fn copy_random_list(
        head: Option<Rc<RefCell<Node>>>,
    ) -> Option<Rc<RefCell<Node>>> {
        head.as_ref()?;

        let mut node_map: HashMap<*const RefCell<Node>, Rc<RefCell<Node>>> =
            HashMap::new();

        // First pass: create all copy nodes
        let mut current = head.clone();
        while let Some(node) = current {
            let ptr = node.as_ptr();
            let copy = Rc::new(RefCell::new(Node::new(node.borrow().val)));
            node_map.insert(ptr, copy);
            current = node.borrow_mut().next.take();
        }

        // Second pass: set next and random pointers
        let mut current = head.clone();
        while let Some(node) = current {
            let ptr = node.as_ptr();
            let copy = node_map.get(&ptr).unwrap().clone();

            // Set next pointer
            if let Some(ref next_node) = node.borrow().next {
                let next_ptr = next_node.as_ptr();
                copy.borrow_mut().next =
                    node_map.get(&next_ptr).cloned();
            }

            // Set random pointer
            if let Some(ref random_node) = node.borrow().random {
                let random_ptr = random_node.as_ptr();
                copy.borrow_mut().random = node_map.get(&random_ptr).cloned();
            }

            current = node.borrow_mut().next.take();
        }

        let head_ptr = head.as_ref().unwrap().as_ptr();
        node_map.remove(&head_ptr)
    }
}

pub struct Solution;

Go

copy_list_with_random_pointer_hash_map.go

package golang

type Node struct {
    Val    int
    Next   *Node
    Random *Node
}

func copyRandomList(head *Node) *Node {
    if head == nil {
        return nil
    }

    // Map original nodes to their copies
    nodeMap := make(map[*Node]*Node)

    // First pass: create all copy nodes
    current := head
    for current != nil {
        nodeMap[current] = &Node{Val: current.Val}
        current = current.Next
    }

    // Second pass: set next and random pointers
    current = head
    for current != nil {
        copyNode := nodeMap[current]
        if current.Next != nil {
            copyNode.Next = nodeMap[current.Next]
        }
        if current.Random != nil {
            copyNode.Random = nodeMap[current.Random]
        }
        current = current.Next
    }

    return nodeMap[head]
}

Approach 2: Interweaving (Constant Space)

advanced

Instead of a hash map, interweave the clones into the original list temporarily. After the first pass, the structure is: original → clone → original → clone → .... In the second pass, the original node’s random neighbor is exactly one step away from the clone’s random neighbor. In the third pass, separate the two lists and restore the original.

This technique eliminates external storage for the mapping by reusing the list structure itself as a pointer table.

⏱ Time O(n) Three passes 💾 Space O(1) Only pointers, no extra map

Step-by-step Example

Input: [[7,null],[13,0]]

Original: 7 → 13

Step	Structure	Action
1	7 → 7’ → 13 → 13’	Interleave clones
2	7’ → null, 13’ → 7’	Set random pointers
3	7 → 13 (restored), 7’ → 13’ → null	Separate lists

Pseudocode

function copyRandomListInterweave(head):
    if head is null:
        return null

    // Pass 1: Interweave
    current = head
    while current != null:
        copy = Node(current.val)
        copy.next = current.next
        current.next = copy
        current = copy.next

    // Pass 2: Set random pointers
    current = head
    while current != null:
        if current.random != null:
            current.next.random = current.random.next
        current = current.next.next

    // Pass 3: Separate lists
    current = head
    copyHead = head.next
    while current != null:
        copy = current.next
        current.next = copy.next
        copy.next = copy.next.next if copy.next else null
        current = current.next

    return copyHead

Solution Code

Python

copy_list_with_random_pointer_interweave.py

from typing import Optional


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


def copyRandomList(head: Optional[Node]) -> Optional[Node]:
    if not head:
        return None

    # First pass: create copies and interleave them
    # original -> copy -> original -> copy -> ...
    current = head
    while current:
        copy = Node(current.val)
        copy.next = current.next
        current.next = copy
        current = copy.next

    # Second pass: set random pointers for copy nodes
    current = head
    while current:
        if current.random:
            current.next.random = current.random.next
        current = current.next.next

    # Third pass: restore original list and extract copy list
    current = head
    copy_head = head.next
    while current:
        copy = current.next
        current.next = copy.next
        copy.next = copy.next.next if copy.next else None
        current = current.next

    return copy_head


# Test cases
def print_list(head: Optional[Node]):
    result = []
    current = head
    while current:
        result.append((current.val, current.random.val if current.random else None))
        current = current.next
    return result


# Example 1: [[7,None],[13,0],[11,4],[10,2],[1,0]]
node1 = Node(7)
node2 = Node(13)
node3 = Node(11)
node4 = Node(10)
node5 = Node(1)

node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5

node1.random = None
node2.random = node1
node3.random = node5
node4.random = node3
node5.random = node1

copy = copyRandomList(node1)
print(print_list(copy))  # [(7, None), (13, 7), (11, 1), (10, 11), (1, 7)]

# Example 2: [[1,1],[2,1]]
node6 = Node(1)
node7 = Node(2)
node6.next = node7
node6.random = node6
node7.random = node6

copy2 = copyRandomList(node6)
print(print_list(copy2))  # [(1, 1), (2, 1)]

C++

copy_list_with_random_pointer_interweave.cpp

#include <unordered_map>
using namespace std;

class Node {
public:
    int val;
    Node* next;
    Node* random;

    Node(int _val) : val(_val), next(NULL), random(NULL) {}
};

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (!head) return NULL;

        // First pass: create copies and interleave them
        // original -> copy -> original -> copy -> ...
        Node* current = head;
        while (current) {
            Node* copy = new Node(current->val);
            copy->next = current->next;
            current->next = copy;
            current = copy->next;
        }

        // Second pass: set random pointers for copy nodes
        current = head;
        while (current) {
            if (current->random) {
                current->next->random = current->random->next;
            }
            current = current->next->next;
        }

        // Third pass: restore original list and extract copy list
        current = head;
        Node* copyHead = head->next;
        while (current) {
            Node* copy = current->next;
            current->next = copy->next;
            copy->next = copy->next ? copy->next->next : NULL;
            current = current->next;
        }

        return copyHead;
    }
};

Java

copy_list_with_random_pointer_interweave.java

class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}

class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) return null;

        // First pass: create copies and interleave them
        // original -> copy -> original -> copy -> ...
        Node current = head;
        while (current != null) {
            Node copy = new Node(current.val);
            copy.next = current.next;
            current.next = copy;
            current = copy.next;
        }

        // Second pass: set random pointers for copy nodes
        current = head;
        while (current != null) {
            if (current.random != null) {
                current.next.random = current.random.next;
            }
            current = current.next.next;
        }

        // Third pass: restore original list and extract copy list
        current = head;
        Node copyHead = head.next;
        while (current != null) {
            Node copy = current.next;
            current.next = copy.next;
            copy.next = copy.next != null ? copy.next.next : null;
            current = current.next;
        }

        return copyHead;
    }
}

JavaScript

copy_list_with_random_pointer_interweave.js

/**
 * // Definition for a Node.
 * function Node(val, next, random) {
 *    this.val = val;
 *    this.next = next;
 *    this.random = random;
 * };
 */

function copyRandomList(head) {
    if (!head) return null;

    // First pass: create copies and interleave them
    // original -> copy -> original -> copy -> ...
    let current = head;
    while (current) {
        const copy = new Node(current.val);
        copy.next = current.next;
        current.next = copy;
        current = copy.next;
    }

    // Second pass: set random pointers for copy nodes
    current = head;
    while (current) {
        if (current.random) {
            current.next.random = current.random.next;
        }
        current = current.next.next;
    }

    // Third pass: restore original list and extract copy list
    current = head;
    const copyHead = head.next;
    while (current) {
        const copy = current.next;
        current.next = copy.next;
        copy.next = copy.next ? copy.next.next : null;
        current = current.next;
    }

    return copyHead;
}

Rust

copy_list_with_random_pointer_interweave.rs

use std::cell::RefCell;
use std::rc::Rc;

#[derive(Clone)]
pub struct Node {
    pub val: i32,
    pub next: Option<Rc<RefCell<Node>>>,
    pub random: Option<Rc<RefCell<Node>>>,
}

impl Node {
    pub fn new(val: i32) -> Self {
        Node {
            val,
            next: None,
            random: None,
        }
    }
}

impl Solution {
    pub fn copy_random_list(
        head: Option<Rc<RefCell<Node>>>,
    ) -> Option<Rc<RefCell<Node>>> {
        let head = head?;

        // First pass: create copies and interleave them
        // original -> copy -> original -> copy -> ...
        let mut current = Some(head.clone());
        while let Some(node) = current {
            let copy = Rc::new(RefCell::new(Node::new(node.borrow().val)));
            let next = node.borrow_mut().next.take();
            node.borrow_mut().next = Some(copy.clone());
            copy.borrow_mut().next = next;
            current = copy.borrow_mut().next.take();
        }

        // Second pass: set random pointers for copy nodes
        let mut current = Some(head.clone());
        while let Some(node) = current {
            let copy = node.borrow().next.clone();
            if let Some(ref copy_node) = copy {
                if let Some(ref random_node) = node.borrow().random {
                    copy_node.borrow_mut().random =
                        random_node.borrow().next.clone();
                }
            }
            current = copy.and_then(|c| c.borrow_mut().next.take());
        }

        // Third pass: restore original list and extract copy list
        let mut current = Some(head.clone());
        let copy_head = head.borrow().next.clone();

        while let Some(node) = current {
            let copy = node.borrow_mut().next.take();
            if let Some(ref copy_node) = copy {
                node.borrow_mut().next = copy_node.borrow_mut().next.take();
            }
            current = node.borrow_mut().next.take();
        }

        copy_head
    }
}

pub struct Solution;

Go

copy_list_with_random_pointer_interweave.go

package golang

type Node struct {
    Val    int
    Next   *Node
    Random *Node
}

func copyRandomList(head *Node) *Node {
    if head == nil {
        return nil
    }

    // First pass: create copies and interleave them
    // original -> copy -> original -> copy -> ...
    current := head
    for current != nil {
        copy := &Node{Val: current.Val}
        copy.Next = current.Next
        current.Next = copy
        current = copy.Next
    }

    // Second pass: set random pointers for copy nodes
    current = head
    for current != nil {
        if current.Random != nil {
            current.Next.Random = current.Random.Next
        }
        current = current.Next.Next
    }

    // Third pass: restore original list and extract copy list
    current = head
    copyHead := head.Next
    for current != nil {
        copy := current.Next
        current.Next = copy.Next
        if copy.Next != nil {
            copy.Next = copy.Next.Next
        }
        current = current.Next
    }

    return copyHead
}

Approach 3: Space-Optimized Variant

✓ Simple

A third approach demonstrating an alternative technique for solving this problem. This implementation optimizes either time or space complexity compared to the previous approaches.

⏱ Time O(n) Optimized complexity 💾 Space O(1) Efficient space usage

Pseudocode

function approach3():
    // Implementation approach goes here

Solution Code

Python

copy_list_with_random_pointer_space_optimized.py

"""
Solution for Copy List with Random Pointer
"""

def solve():
    """Implementation for approach 3 of Copy List with Random Pointer"""
    pass

if __name__ == "__main__":
    print("Solution ready")

C++

copy_list_with_random_pointer_space_optimized.cpp

#include <bits/stdc++.h>
using namespace std;

// Solution for Copy List with Random Pointer
// Approach 3: Implementation

int main() {{
    // Main implementation goes here
    return 0;
}}

Java

CopyListWithRandomPointerSpaceOptimized.java

/**
 * Solution for Copy List with Random Pointer
 * Approach 3
 */
public class CopyListWithRandomPointerSpaceOptimized {{

    public static void main(String[] args) {{
        // Implementation goes here
    }}
}}

JavaScript

copy_list_with_random_pointer_space_optimized.js

/**
 * Solution for Copy List with Random Pointer
 * Approach 3
 */

function solve() {{
    // Implementation goes here
}}

module.exports = solve;

Rust

copy_list_with_random_pointer_space_optimized.rs

/// Solution for Copy List with Random Pointer
/// Approach 3

fn main() {{
    println!("Solution implementation");
}}

Go

copy_list_with_random_pointer_space_optimized.go

package main

import "fmt"

// Solution for Copy List with Random Pointer
// Approach 3

func main() {{
    fmt.Println("Solution implementation")
}}

Common Mistakes

Watch for these pitfalls

• Forgetting that random pointers can point backward, forward, or to themselves — they are not bound by list order.
• In the hash map approach, checking if a pointer exists before accessing the map; always use a map that safely returns null for missing keys.
• In the interweaving approach, losing track of the original list structure during separation; restore it carefully in pass 3.
• Confusing shallow copy (copying pointers) with deep copy (creating new nodes); this problem requires a full deep copy.
• Not handling the null head case or null pointers within the random field.

Related Problems

• Reverse Linked List ↗ Easy #206
• Merge Two Sorted Lists ↗ Easy #21
• Linked List Cycle ↗ Easy #141
• Remove Nth Node From End of List ↗ Medium #19
• Add Two Numbers ↗ Medium #2

Interview Tips

Key trade-offs to discuss

• Hash Map vs. Interweaving: Hash map is clearer and safer; interweaving is more elegant and space-optimal. Most interviewers accept either.
• Why two passes minimum? Random pointers can point forward or backward; you cannot build the copy in a single pass without either a map or temporary storage.
• Handling cycles: The algorithm does not assume the list is acyclic, so it correctly handles cases where random pointers create cycles (e.g., a node’s random points back to itself).
• Testing: Always test with null head, single node, and random pointers that form cycles or span the entire list.
• Distinguishing deep from shallow: Explicitly mention that you are creating new nodes, not just copying pointers. Shallow copy would fail this problem.

← Previous
#137 Single Number II Next
#139 Word Break →