Problem Overview

This problem is an extension of the classic linked list cloning problem. Along with the usual next pointer, every node also contains a random pointer that can point to any node in the list or be null.

Our task is to create a deep copy of the entire linked list.

A deep copy means:

  • Every node in the new list is a completely new object.
  • The next pointers should preserve the original ordering.
  • The random pointers should point to the corresponding copied nodes—not the original ones.

Example

Original List:

A(3) ──► B(7) ──► C(4) ──► D(5)
 |        |         |        |
 ↓        ↓         ↓        ↓
null      D         A        B

The copied list should have the exact same structure:

A'(3) ──► B'(7) ──► C'(4) ──► D'(5)
 |         |          |         |
 ↓         ↓          ↓         ↓
null       D'         A'        B'

Notice that every pointer in the copied list points only to copied nodes.

Key Observation

The biggest challenge is the random pointer.

While copying a node, we don’t necessarily know whether the node pointed to by random has already been copied.

For example:

1 -> 2 -> 3

1.random -> 3

When copying node 1, node 3 may not have been copied yet.

So we need a way to quickly find the copied version of any original node.

This naturally suggests using a hash map.

Idea

Maintain a dictionary that maps:

Original Node  --->  Copied Node

For every node in the original list, we store its corresponding clone.

oldToCopy = {
    original_node1 : copy_node1,
    original_node2 : copy_node2,
    ...
}

Once this mapping exists, assigning both next and random becomes straightforward.

Why 

None

is Added to the Dictionary

One small but elegant trick is:

oldToCopy = {None: None}

Why?

Some nodes may have

next = None

or

random = None

Instead of writing special cases like

if cur.random:
    copy.random = oldToCopy[cur.random]
else:
    copy.random = None

we can simply write

copy.random = oldToCopy[cur.random]

because

oldToCopy[None] = None

This keeps the code clean and avoids unnecessary conditionals.

First Pass: Copy Every Node

We first create a copy of every node without connecting anything.

cur = head

while cur:
    copy = Node(cur.val)
    oldToCopy[cur] = copy
    cur = cur.next

At the end of this pass, we have:

Original:   A -> B -> C

Dictionary:

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

But none of the pointers have been assigned yet.

Second Pass: Connect the Pointers

Now every copied node already exists.

So we can safely connect both next and random.

cur = head

while cur:
    copy = oldToCopy[cur]

    copy.next = oldToCopy[cur.next]
    copy.random = oldToCopy[cur.random]

    cur = cur.next

Suppose

Original

A.random -> C
A.next   -> B

Using the dictionary,

copy.random = oldToCopy[C] = C'
copy.next   = oldToCopy[B] = B'

Everything is connected correctly.

Dry Run

Consider:

1 -> 2 -> 3

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

Pass 1

Create copies.

Dictionary

1 -> 1'
2 -> 2'
3 -> 3'

Pass 2

For node 1:

1'.next = 2'
1'.random = 3'

For node 2:

2'.next = 3'
2'.random = 1'

For node 3:

3'.next = None
3'.random = 2'

The copied list now perfectly mirrors the original.

Complete Solution

from typing import Optional

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: 'Optional[Node]') -> 'Optional[Node]':
        oldToCopy = {None: None}

        cur = head

        # First pass: create copies
        while cur:
            copy = Node(cur.val)
            oldToCopy[cur] = copy
            cur = cur.next

        cur = head

        # Second pass: assign next and random pointers
        while cur:
            copy = oldToCopy[cur]
            copy.next = oldToCopy[cur.next]
            copy.random = oldToCopy[cur.random]
            cur = cur.next

        return oldToCopy[head]

Complexity Analysis

Time Complexity

  • First traversal: O(n)
  • Second traversal: O(n)

Overall:

O(n)

Space Complexity

The hash map stores one copied node for every original node.

O(n)

Why This Approach Works

The core idea is to separate node creation from pointer assignment.

  • Pass 1 ensures every copied node already exists.
  • Pass 2 uses the hash map to connect next and random pointers in constant time.

This avoids complicated forward references and keeps the implementation simple, readable, and efficient.

This is one of the cleanest solutions to the problem and is the standard hash map approach for cloning a linked list with random pointers.