Copy List with Random Pointer

Medium Problem 58 of 151 Java and Python

Problem

Each node of a linked list has a next pointer and a random pointer that may point to any node in the list or be null.

Return a deep copy of the list: brand-new nodes whose next and random pointers mirror the original, with no pointer into the original list.

Example 1

Input: [[7, null], [13, 0], [11, 4], [10, 2], [1, 0]] (value, index of random)
Output: a new list with the same shape

Example 2

Input: [[1, 1], [2, 1]]
Output: [[1, 1], [2, 1]]
Why: Both random pointers point to the second node.

Constraints

0 ≤ n ≤ 1000
Node.random is null or points to a node in the list.

Explanation

The tricky part is random: it can point forward to a node you have not copied yet. Solve it in two passes. First create a copy of every node, remembering original → copy. Then wire up next and random using that mapping.

The O(1)-space trick stores the mapping in the list itself: put each copy right after its original (A → A' → B → B'). Then copy.random = original.random.next.

Approach 1 · Better

Map from original to copy

Time O(n)
Space O(n)

First pass: copy every node into a map. Second pass: set each copy's next and random through the map.

For each node, map[node] = new Node(node.val).
For each node, map[node].next = map[node.next], map[node].random = map[node.random].
Return map[head].

Java

import java.util.*;

class Solution {
    public Node copyRandomList(Node head) {
        Map<Node, Node> copy = new HashMap<>();
        for (Node node = head; node != null; node = node.next) {
            copy.put(node, new Node(node.val));
        }
        for (Node node = head; node != null; node = node.next) {
            copy.get(node).next = copy.get(node.next);
            copy.get(node).random = copy.get(node.random);
        }
        return copy.get(head);
    }
}

Python

class Solution:
    def copyRandomList(self, head: "Optional[Node]") -> "Optional[Node]":
        copy = {None: None}
        node = head
        while node:
            copy[node] = Node(node.val)
            node = node.next
        node = head
        while node:
            copy[node].next = copy[node.next]
            copy[node].random = copy[node.random]
            node = node.next
        return copy[head]

Approach 2 · Optimal

Interleave the copies

Time O(n)
Space O(1) besides the copy

Insert each copy right after its original, set the random pointers, then split the two lists apart.

For each node A, insert A' between A and A.next.
For each original A: if A.random exists, A'.random = A.random.next.
Separate: restore A.next to the next original and link the copies together.

Java

class Solution {
    public Node copyRandomList(Node head) {
        for (Node node = head; node != null; node = node.next.next) {
            Node copy = new Node(node.val);
            copy.next = node.next;
            node.next = copy;
        }
        for (Node node = head; node != null; node = node.next.next) {
            if (node.random != null) {
                node.next.random = node.random.next;
            }
        }
        Node dummy = new Node(0);
        Node tail = dummy;
        for (Node node = head; node != null; node = node.next) {
            tail.next = node.next;
            tail = tail.next;
            node.next = node.next.next;
        }
        return dummy.next;
    }
}

Python

class Solution:
    def copyRandomList(self, head: "Optional[Node]") -> "Optional[Node]":
        node = head
        while node:
            node.next = Node(node.val, node.next)
            node = node.next.next
        node = head
        while node:
            if node.random:
                node.next.random = node.random.next
            node = node.next.next
        dummy = tail = Node(0)
        node = head
        while node:
            tail.next = node.next
            tail = tail.next
            node.next = node.next.next
            node = node.next
        return dummy.next

Complexity compared

Approach	Time	Space
Better Map from original to copy	O(n)	O(n)
Optimal Interleave the copies	O(n)	O(1) besides the copy

Key takeaways

"Old node → new node" maps are the standard tool for cloning anything with pointers, including graphs (Clone Graph).
The interleaving version must restore the original list; the grader checks it.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem