LeetCode 138: Copy List with Random Pointer

Problem Restatement

We are given the head of a linked list.

Each node contains:

Field	Meaning
`val`	Integer value
`next`	Pointer to the next node
`random`	Pointer to any node in the list or `None`

We need to create a deep copy of the entire list.

The copied list must contain entirely new nodes.

Every copied node should preserve:

The same val
The same next structure
The same random structure

But no copied node may point to an original node.

LeetCode describes this as constructing a deep copy where copied nodes replicate both the next and random relationships of the original list. (leetcode.com)

Examples

Example 1:

7 -> 13 -> 11 -> 10 -> 1

Suppose:

Node	Random points to
`7`	`None`
`13`	`7`
`11`	`1`
`10`	`11`
`1`	`7`

The copied list must have the same structure:

7' -> 13' -> 11' -> 10' -> 1'

and:

Copied node	Random points to
`7'`	`None`
`13'`	`7'`
`11'`	`1'`
`10'`	`11'`
`1'`	`7'`

Every target must be another copied node, not an original node.

Example 2:

1 -> 2

with:

1.random -> 2
2.random -> 2

The copied structure must preserve those relationships.

Input and Output

Item	Meaning
Input	`head: Optional[Node]`
Output	Head of the deep-copied list
`next`	Standard linked-list pointer
`random`	May point anywhere in the list or `None`
Main requirement	Deep copy

Function shape:

class Solution:
    def copyRandomList(self, head: "Node") -> "Node":
        ...

First Thought: Copy Nodes One by One

A first attempt might:

Copy each node.
Connect copied next pointers.
Somehow copy random pointers later.

The difficulty is:

original.random -> original node

must become:

copy.random -> copied node

So whenever we see an original node, we must know its corresponding copied node.

This naturally suggests a hash map.

Key Insight

Store the relationship:

original_node -> copied_node

Then:

First pass:
- create all copied nodes
- fill the map
Second pass:
- connect next
- connect random

This guarantees every original node has exactly one copied node.

Two-Pass Hash Map Algorithm

First pass:

For every original node:

copies[curr] = Node(curr.val)

Second pass:

For every original node:

copies[curr].next = copies.get(curr.next)
copies[curr].random = copies.get(curr.random)

Finally:

return copies[head]

Why `.get()` Works

The last node has:

curr.next = None

Some random pointers are also:

None

Using:

copies.get(None)

returns:

None

which correctly preserves null pointers.

Correctness

During the first pass, the algorithm creates exactly one copied node for every original node and stores the mapping in copies.

Therefore, for every original node u, copies[u] is the unique copied node corresponding to u.

During the second pass:

copies[curr].next = copies.get(curr.next)

assigns the copied node corresponding to curr.next.

Similarly:

copies[curr].random = copies.get(curr.random)

assigns the copied node corresponding to curr.random.

Thus, every next and random relationship from the original list is reproduced exactly between copied nodes.

Since every copied node is newly allocated, no copied node points to an original node. Therefore, the returned list is a correct deep copy.

Complexity

Let n be the number of nodes.

Metric	Value	Why
Time	`O(n)`	Two linear passes
Space	`O(n)`	Hash map stores all nodes

Implementation

# 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

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

        copies = {}

        curr = head

        while curr:
            copies[curr] = Node(curr.val)
            curr = curr.next

        curr = head

        while curr:
            copies[curr].next = copies.get(curr.next)
            copies[curr].random = copies.get(curr.random)
            curr = curr.next

        return copies[head]

Code Explanation

Handle the empty list:

if head is None:
    return None

Create the mapping dictionary:

copies = {}

The first pass allocates cloned nodes:

while curr:
    copies[curr] = Node(curr.val)
    curr = curr.next

At this point:

original node -> copied node

exists for every node.

The second pass connects pointers:

copies[curr].next = copies.get(curr.next)
copies[curr].random = copies.get(curr.random)

The copied node now points only to copied nodes.

Finally:

return copies[head]

returns the copied head.

O(1) Extra Space Trick

There is also a more advanced solution without a hash map.

The idea:

Insert copied nodes directly after original nodes.
Use interleaving to connect random pointers.
Separate the two lists.

Example:

Before:

A -> B -> C

After inserting copies:

A -> A' -> B -> B' -> C -> C'

Then:

A'.random = A.random.next

because:

A.random.next

is the copied version of A.random.

Finally, detach the copied list.

This solution uses O(1) extra space but is harder to derive.

O(1) Space Implementation

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

        curr = head

        while curr:
            copy = Node(curr.val)
            copy.next = curr.next
            curr.next = copy
            curr = copy.next

        curr = head

        while curr:
            if curr.random:
                curr.next.random = curr.random.next

            curr = curr.next.next

        dummy = Node(0)
        copy_curr = dummy
        curr = head

        while curr:
            copy = curr.next

            curr.next = copy.next
            copy_curr.next = copy

            copy_curr = copy
            curr = curr.next

        return dummy.next

Testing

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

def serialize(head: Node | None):
    nodes = []
    index = {}
    curr = head
    i = 0

    while curr:
        index[curr] = i
        nodes.append(curr)
        curr = curr.next
        i += 1

    result = []

    for node in nodes:
        random_index = (
            index[node.random]
            if node.random is not None
            else None
        )

        result.append([node.val, random_index])

    return result

def run_tests():
    s = Solution()

    n1 = Node(7)
    n2 = Node(13)
    n3 = Node(11)
    n4 = Node(10)
    n5 = Node(1)

    n1.next = n2
    n2.next = n3
    n3.next = n4
    n4.next = n5

    n1.random = None
    n2.random = n1
    n3.random = n5
    n4.random = n3
    n5.random = n1

    copied = s.copyRandomList(n1)

    assert serialize(copied) == [
        [7, None],
        [13, 0],
        [11, 4],
        [10, 2],
        [1, 0],
    ]

    assert copied is not n1
    assert copied.next is not n2

    single = Node(1)
    single.random = single

    single_copy = s.copyRandomList(single)

    assert single_copy is not single
    assert single_copy.random is single_copy

    assert s.copyRandomList(None) is None

    print("all tests passed")

run_tests()

Test meaning:

Test	Why
Standard multi-node example	Verifies `next` and `random` reconstruction
Identity checks	Confirms deep copy
Self-random pointer	Node points to itself
Empty list	Handles `None` input