This problem is a classic Linked List interview question that tests your understanding of deep copying and pointer manipulation.

The challenge is not copying the next pointers, but correctly maintaining the relationships created by the random pointers.

Problem Statement

Given a linked list where each node contains:

int val;
Node next;
Node random;

Create a deep copy of the list.

The copied list should:

• Contain completely new nodes.
• Preserve the next relationships.
• Preserve the random relationships.
• Not reference any node from the original list.

Brute Force Intuition

For every original node:

• Create a copy node.
• Store mapping:

Original Node -> Copied Node

using a HashMap.

After creating all nodes:

• Traverse again.
• Connect next pointers.
• Connect random pointers using the map.

Interview Explanation

Since random pointers can point anywhere in the list, we first create a clone of every node and store the original-to-copy mapping in a HashMap. During a second traversal, we use this mapping to connect both next and random pointers correctly.

Complexity

Time  : O(n)

Space : O(n)

Moving Towards the Optimal Solution

Can we avoid the HashMap?

Notice:

Original:
A -> B -> C

What if we insert cloned nodes in between?

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

Now every clone sits immediately after its original node.

This creates a shortcut that allows us to assign random pointers without a HashMap.

Key Observation

Suppose:

A.random = C

After inserting clones:

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

Then:

A'.random = C'

And:

C' = A.random.next

Therefore:

copy.random = original.random.next;

This is the entire trick behind the optimal solution.

Optimal Approach

Step 1

Insert cloned nodes between originals.

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

Step 2

Assign random pointers.

copy.random = original.random.next;

Step 3

Separate both lists.

Original:

A -> B -> C

Copied:

A' -> B' -> C'

Dry Run

Original List

1 -> 2 -> 3

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

After Inserting Copies

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

Setting Random Pointers

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

using:

cur.next.random = cur.random.next;

Separate Lists

Original:

1 -> 2 -> 3

Copied:

1' -> 2' -> 3'

Deep copy created successfully.

Optimal Java Solution

class Solution {

    public Node copyRandomList(Node head) {

        if (head == null)
            return null;

        // Step 1: Insert copied nodes
        Node cur = head;

        while (cur != null) {

            Node copy = new Node(cur.val);

            copy.next = cur.next;
            cur.next = copy;

            cur = copy.next;
        }

        // Step 2: Set random pointers
        cur = head;

        while (cur != null) {

            if (cur.random != null) {
                cur.next.random = cur.random.next;
            }

            cur = cur.next.next;
        }

        // Step 3: Separate original and copied list
        Node dummy = new Node(0);
        Node copyTail = dummy;

        cur = head;

        while (cur != null) {

            Node copy = cur.next;

            cur.next = copy.next;

            copyTail.next = copy;
            copyTail = copy;

            cur = cur.next;
        }

        return dummy.next;
    }
}

Why This Works

By inserting each copied node immediately after its original node:

Original -> Copy

we can access the copied version of any node in O(1) time using:

original.next

This removes the need for a HashMap entirely.

Complexity Analysis

Time  : O(n)

Space : O(1)

No extra HashMap is used.

Pattern Recognition

Whenever you see:

• Clone Linked List
• Random Pointer
• Deep Copy Structure

Think:

Interweave Copies
→ Set Random Pointers
→ Separate Lists

This is the standard optimal interview pattern.

Interview One-Liner

Instead of using a HashMap, I interleave cloned nodes with original nodes, use the adjacency relationship to assign random pointers in O(1), and finally separate the two lists, achieving O(n) time and O(1) extra space.