DSAPrep
MediumLinked List

Copy List with Random Pointer

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 copied list such that the pointers in the original list and copied list represent the same list state. None of the pointers in the new list should point to nodes in the original list.

The linked list is represented in the input/output as a list of n nodes, each represented as a pair [val, random_index], where random_index is the index of the node the random pointer points to, or null.

Your code will only be given the head of the original linked list.

Example 1

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

Example 2

Input: head = [[1,1],[2,1]]
Output: [[1,1],[2,1]]

Example 3

Input: head = [[3,null],[3,0],[3,null]]
Output: [[3,null],[3,0],[3,null]]

Constraints

  • 0 <= n <= 1000
  • -10^4 <= Node.val <= 10^4
  • Node.random is null or is pointing to some node in the linked list.
View original on LeetCode ↗

The next pointers alone would make this a plain list copy. The random pointer is what makes it interesting: when you build the copy of node X, its random target Y might not have been created yet (it could be later in the list, or even X itself). You need a way to look up “the copy of node Y” regardless of visit order.

Small example used below: A(val=1) → B(val=2) → C(val=3), with A.random → C, B.random → null, C.random → A. Draw it as three nodes in a row; a solid arrow between consecutive nodes is next, and curved labels below mark each random target (A.random → C, C.random → A, B.random → null).

Hash Map (Old Node → New Node)

Time O(n)Space O(n)

Make one pass to create a brand-new node for every original node, and store the mapping old_node → new_node in a dictionary. Then make a second pass where each new node’s next and random are set by looking up the mapping for the original node’s next and random — the dictionary handles the case where the random target has not been “reached” yet in list order, since all copies already exist by the second pass.

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


class Solution:
    def copyRandomList(self, head: "Node | None") -> "Node | None":
        if not head:
            return None


        old_to_new = {}
        node = head
        while node:
            old_to_new[node] = Node(node.val)
            node = node.next


        node = head
        while node:
            old_to_new[node].next = old_to_new.get(node.next)
            old_to_new[node].random = old_to_new.get(node.random)
            node = node.next


        return old_to_new[head]

Correct and easy to follow — the .get(...) returns None automatically when node.next or node.random is None. The only downside is the O(n) dictionary mapping every old node to its copy.

Interweaving (O(1) Extra Space)

OptimalTime O(n)Space O(1)

Avoid the hash map by temporarily splicing each copy directly after its original, turning A → B → C into A → A' → B → B' → C → C'. Now the copy of any node’s random target is always right next to that target: node.random.next is the copy of node.random. Once every random pointer is set this way, unweave the two interleaved lists back apart.

class Solution:
    def copyRandomList(self, head: "Node | None") -> "Node | None":
        if not head:
            return None


        # 1. Interweave: A -> A' -> B -> B' -> ...
        node = head
        while node:
            copy = Node(node.val)
            copy.next = node.next
            node.next = copy
            node = copy.next


        # 2. Assign random pointers using the interweaved structure
        node = head
        while node:
            if node.random:
                node.next.random = node.random.next   # copy's random -> copy of node.random
            node = node.next.next


        # 3. Unweave into two separate lists
        node = head
        new_head = head.next
        while node:
            copy = node.next
            node.next = copy.next
            copy.next = copy.next.next if copy.next else None
            node = node.next


        return new_head

Why it’s correct: after interweaving, node.next is always node’s own copy — so for any node.random pointing at some original node Y, Y’s copy is exactly node.random.next. This lets every random pointer be resolved without any auxiliary storage, and the final unweave pass cleanly restores both the original list and produces the fully-linked copy. Complexity: three separate O(n) passes (interweave, assign random, unweave), each touching every node a constant number of times → O(n) time. Only a handful of pointer variables are used, and no data structure scales with n → O(1) extra space — optimal, since producing n new nodes with correct pointers requires visiting every original node at least once.