Introduction

Copy List with Random Pointer means creating a completely separate duplicate linked list.

Each node contains:

  • next pointer
  • random pointer

The task is to:

  • create new nodes
  • preserve next links
  • preserve random links

Example:

Input:
1 -> 2 -> 3

Random:
1 -> 3
2 -> 1
3 -> 2

Output:
Deep copied list with same structure

Explanation:

New nodes are created. Original list remains unchanged.Both next and random connections are preserved.

This problem is one of the most important applications of:

HashMap + Pointer Manipulation

Constraints

0 <= Number of Nodes <= 10^5

Approach 1 : Brute Force (Using HashMap)

Explanations:

Explanation:

The idea is:

  • create copy of every node
  • store mapping in HashMap
  • reconnect next and random pointers

Steps:

  1. Copy all nodes.
  2. Store original -> copy mapping.
  3. Connect next pointers.
  4. Connect random pointers.

This is the most common interview solution.

Dry Run

Original:1 -> 2 -> 3

Copy nodes:
1' 2' 3'

Map:
1 -> 1'
2 -> 2'
3 -> 3'

Random links are copied using HashMap.

Practice :

Complexity Analysis :

Time Complexity:- O(n)Explanation :
Each node is visited twice.

Space Complexity:- O(n)
Explanation :
HashMap stores node mapping.

Approach 2 : Optimal Solution(Using Interleaving Technique)

Explanations:

Explanation:

This is the most optimized and interview-preferred solution.

The idea is:

  • insert copied nodes beside originals
  • connect random pointers
  • separate copied list

This avoids extra HashMap usage.

Dry Run

Original:
1 -> 2 -> 3

Insert copies:
1 -> 1' -> 2 -> 2' -> 3 -> 3'

Connect random pointers.
Separate copied list.
Deep copy completed.

Practice :

Complexity Analysis :

Time Complexity:- O(n)Explanation :
Each node is processed efficiently.

Space Complexity:- O(1)
Explanation :
No extra HashMap is used.

Why This Problem is Important

This problem builds the foundation for:

  • Deep Copy
  • HashMap usage
  • Pointer manipulation
  • Complex linked structures
  • Memory optimization

Real-World Applications

Deep copy concepts are used in:

  • Game state cloning
  • Undo systems
  • Graph duplication
  • Memory management
  • Data replication systems

Common Beginner Mistakes

  • Incorrect random pointer mapping
  • Forgetting deep copy concept
  • Breaking original list
  • NULL pointer errors
  • Incorrect separation logic

Interview Tip

Interviewers often expect:

  • deep copy understanding
  • HashMap optimization
  • pointer manipulation
  • O(1) space optimization

Always explain:

  • difference between shallow and deep copy
  • how random pointers are preserved

Related Questions

  • Clone Graph
  • Linked List Cycle
  • Reverse Linked List
  • Merge Two Sorted Lists
  • Deep Copy Problems

Final Takeaway

The Copy List with Random Pointer problem is one of the most important advanced linked list interview problems.

It teaches:

  • deep copy logic
  • pointer manipulation
  • random pointer handling
  • memory optimization

Understanding this problem builds a strong foundation for:

  • advanced linked list problems
  • graph cloning concepts
  • interview-level data structure questions.