LeetCode 138 - Copy List with Random Pointer

LeetCode Problem 138

Difficulty: 🟡 Medium
Topics: Hash Table, Linked List

Solution

Problem Understanding

This problem asks us to create a completely independent copy of a linked list where each node contains two pointers:

• next, which points to the next node in the list
• random, which can point to any node in the list or null

The key requirement is that the copied list must be a true deep copy. That means every node in the new list must be newly allocated, and none of the pointers in the copied list can reference nodes from the original list.

The input is given conceptually as a list of pairs:

[val, random_index]

Here:

• val is the node's value
• random_index tells us which node the random pointer references
• null means the random pointer does not point anywhere

However, the actual function does not receive this array representation. Instead, it receives only the head node of the linked list. We must traverse the structure ourselves and reconstruct both pointer relationships.

The challenge comes from the random pointers. Unlike a normal linked list, nodes may point backward, forward, or even to themselves. This means a simple sequential copy is not enough because when we copy a node, its random target may not yet exist.

The constraints are relatively small:

• Up to 1000 nodes
• Node values range from -10^4 to 10^4

These constraints allow an O(n) or even O(n^2) solution to pass, but the problem is fundamentally about correctly preserving pointer relationships rather than handling huge input sizes.

Several edge cases are important:

• The list may be empty
• A node's random pointer may be null
• Multiple nodes may point to the same random target
• A node may point to itself through random
• Random pointers may create cycles unrelated to the next chain

A naive implementation can easily fail by accidentally reusing original nodes or by losing the mapping between original nodes and copied nodes.

Approaches

Brute Force Approach

A brute force strategy would attempt to recreate each node and then, for every original node, search the copied list to locate the corresponding random target.

The process would look like this:

1. Copy all nodes sequentially using the next pointers.
2. For each original node:

• Find the node referenced by random
• Search through the original list to determine its position
• Traverse the copied list again to locate the corresponding copied node
• Assign the copied random pointer

This works because every original node has exactly one corresponding copied node. By repeatedly searching both lists, we can eventually reconstruct the random relationships correctly.

However, this approach is inefficient because every random pointer assignment may require traversing the list again. With n nodes, this can lead to O(n^2) time complexity.

Optimal Approach

The key insight is that we need a fast way to map:

original node -> copied node

A hash map solves this perfectly.

We perform two passes through the list:

1. First pass:

• Create a copy of every node
• Store the mapping in a hash map

2. Second pass:

• Use the hash map to assign:

• next

• random

Since hash map lookups are O(1) on average, we avoid repeated traversals and achieve linear time complexity.

This approach is ideal because each original node is processed only a constant number of times.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Repeatedly searches lists to locate random targets
Optimal	O(n)	O(n)	Uses a hash map from original nodes to copied nodes

Algorithm Walkthrough

Optimal Hash Map Algorithm

1. Handle the empty list case immediately.

If head is null, there is nothing to copy, so we return null. 2. Create a hash map.

The hash map will store:

original node -> copied node

This mapping allows us to instantly locate the copied version of any original node. 3. Traverse the original list for the first time.

For each original node:

• Create a new node with the same value
• Store the mapping in the hash map

At this stage, we only copy node values. We do not yet assign next or random. 4. Traverse the original list a second time.

For each original node:

• Retrieve its copied node from the hash map

• Set:

• copy.next = hashmap[original.next]

• copy.random = hashmap[original.random]

Since every node already exists in the hash map, all pointer assignments become straightforward. 5. Return the copied head.

The copied head is simply:

hashmap[head]

Why it works

The algorithm works because every original node receives exactly one copied node, and the hash map preserves that relationship throughout the process.

During the second traversal, every pointer assignment is redirected from original nodes to copied nodes using the mapping. Therefore:

• All copied nodes reference other copied nodes
• No copied node references an original node
• The exact structure of both next and random relationships is preserved

This guarantees a valid deep copy.

Python Solution

"""
# Definition for a Node.
class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random
"""

from typing import Optional

class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        if not head:
            return None

        old_to_new = {}

        current = head
        while current:
            old_to_new[current] = Node(current.val)
            current = current.next

        current = head
        while current:
            copy_node = old_to_new[current]

            copy_node.next = old_to_new.get(current.next)
            copy_node.random = old_to_new.get(current.random)

            current = current.next

        return old_to_new[head]

The implementation begins by handling the empty list case. This prevents unnecessary work and avoids dereferencing None.

The dictionary old_to_new is the core data structure. Each original node is used as a key, and its copied node becomes the value.

The first traversal creates all copied nodes. At this point, only node values are copied because some referenced nodes may not yet exist.

The second traversal establishes the pointer relationships. Since every copied node already exists in the dictionary, assigning next and random becomes a direct lookup operation.

The use of .get() is important because current.next or current.random may be None. In that case, the lookup safely returns None.

Finally, the copied head node is returned from the hash map.

Go Solution

/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Next *Node
 *     Random *Node
 * }
 */

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

    oldToNew := make(map[*Node]*Node)

    current := head
    for current != nil {
        oldToNew[current] = &Node{
            Val: current.Val,
        }
        current = current.Next
    }

    current = head
    for current != nil {
        copyNode := oldToNew[current]

        copyNode.Next = oldToNew[current.Next]
        copyNode.Random = oldToNew[current.Random]

        current = current.Next
    }

    return oldToNew[head]
}

The Go implementation follows the exact same algorithmic structure as the Python version.

A Go map is used to associate original node pointers with copied node pointers:

map[*Node]*Node

Go maps return the zero value when a key does not exist. Since the zero value for pointers is nil, we can safely assign:

copyNode.Next = oldToNew[current.Next]

even when current.Next is nil.

Unlike Python, Go requires explicit pointer allocation using &Node{}.

Worked Examples

Example 1

Input:

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

Original Structure

Node	Value	Next	Random
A	7	B	null
B	13	C	A
C	11	D	E
D	10	E	C
E	1	null	A

First Pass

We create copied nodes:

Original	Copy
A	A'
B	B'
C	C'
D	D'
E	E'

At this stage:

A', B', C', D', E'

exist, but pointers are not assigned yet.

Second Pass

Processing A

A.next = B
A.random = null

Assign:

A'.next = B'
A'.random = null

Processing B

B.next = C
B.random = A

Assign:

B'.next = C'
B'.random = A'

Processing C

C.random = E

Assign:

C'.random = E'

Processing D

D.random = C

Assign:

D'.random = C'

Processing E

E.random = A

Assign:

E'.random = A'

The copied list now exactly matches the original structure.

Example 2

Input:

[[1,1],[2,1]]

Original Structure

Node	Random
A	B
B	B

Copy Construction

Original	Copy
A	A'
B	B'

Assignments:

A'.random = B'
B'.random = B'

This example demonstrates that multiple nodes can point to the same target.

Example 3

Input:

[[3,null],[3,0],[3,null]]

Original Structure

Node	Random
A	null
B	A
C	null

Assignments:

A'.random = null
B'.random = A'
C'.random = null

This confirms that duplicate values do not matter because nodes are identified by reference, not by value.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each node is visited twice
Space	O(n)	Hash map stores one copied node per original node

The algorithm performs two linear traversals of the linked list. Each node insertion and lookup in the hash map is O(1) on average, so the total runtime remains linear.

The additional space comes from the hash map and the copied nodes themselves. Since we create exactly one copied node per original node, the auxiliary space complexity is O(n).

Test Cases

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

class Solution:
    def copyRandomList(self, head):
        if not head:
            return None

        old_to_new = {}

        current = head
        while current:
            old_to_new[current] = Node(current.val)
            current = current.next

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

        return old_to_new[head]

def linked_list_to_array(head):
    nodes = []
    node_to_index = {}

    current = head
    index = 0

    while current:
        node_to_index[current] = index
        nodes.append(current)
        current = current.next
        index += 1

    result = []

    for node in nodes:
        random_index = (
            node_to_index[node.random]
            if node.random is not None
            else None
        )
        result.append([node.val, random_index])

    return result

solution = Solution()

# Test 1: Empty list
assert solution.copyRandomList(None) is None  # handles empty input

# Test 2: Single node with null random
a = Node(1)
copied = solution.copyRandomList(a)
assert linked_list_to_array(copied) == [[1, None]]  # single node

# Test 3: Single node pointing to itself
a = Node(1)
a.random = a
copied = solution.copyRandomList(a)
assert linked_list_to_array(copied) == [[1, 0]]  # self-random pointer

# Test 4: Two nodes sharing same random target
a = Node(1)
b = Node(2)

a.next = b

a.random = b
b.random = b

copied = solution.copyRandomList(a)
assert linked_list_to_array(copied) == [[1, 1], [2, 1]]  # shared target

# Test 5: Problem example 1
a = Node(7)
b = Node(13)
c = Node(11)
d = Node(10)
e = Node(1)

a.next = b
b.next = c
c.next = d
d.next = e

b.random = a
c.random = e
d.random = c
e.random = a

copied = solution.copyRandomList(a)

assert linked_list_to_array(copied) == [
    [7, None],
    [13, 0],
    [11, 4],
    [10, 2],
    [1, 0]
]  # full mixed random structure

# Test 6: Ensure deep copy
a = Node(5)
b = Node(6)

a.next = b
a.random = b
b.random = a

copied = solution.copyRandomList(a)

assert copied is not a  # copied head is different object
assert copied.next is not b  # copied nodes are distinct
assert copied.random is copied.next  # internal references preserved

Test	Why
Empty list	Validates null input handling
Single node with null random	Tests minimal non-empty structure
Self-random pointer	Ensures self references are preserved
Shared random target	Verifies multiple references work correctly
Full example structure	Tests mixed forward and backward random pointers
Deep copy validation	Confirms copied nodes are independent objects

Edge Cases

Empty List

The input head may be null. This is the simplest possible input, but forgetting to handle it can cause dereferencing errors during traversal.

The implementation immediately checks:

if not head:
    return None

This guarantees safe handling before any hash map operations occur.

Self Referencing Random Pointer

A node may point to itself through the random pointer.

For example:

A.random = A

A shallow copy would accidentally preserve the original reference, which violates the deep copy requirement.

The hash map approach handles this naturally because:

copy.random = hashmap[original.random]

When original.random is the original node itself, the copied node receives a reference to its own copied counterpart.

Multiple Nodes Sharing the Same Random Target

Several nodes may point to the same node through random.

For example:

A.random = C
B.random = C

A buggy implementation might accidentally create duplicate copies of C.

The hash map guarantees uniqueness because every original node is copied exactly once. Every lookup for the same original node returns the same copied node.

Duplicate Node Values

Different nodes may contain identical values.

For example:

[3, 3, 3]

If we tried to identify nodes by value, the mapping would become ambiguous.

The implementation avoids this entirely by using node references as hash map keys instead of node values. Even if values are identical, node objects remain distinct.