Clone Linked List with Random Pointer in DSA Typescript - Deep Dive

Overview - Clone Linked List with Random Pointer

What is it?

A linked list with a random pointer is a special list where each node has two pointers: one points to the next node in order, and the other points to any random node in the list or null. Cloning this list means creating a new list that looks exactly the same, including the random connections. This is harder than a normal linked list clone because of the random pointers that can point anywhere. The goal is to make a deep copy so changes to the new list do not affect the original.

Why it matters

Without cloning linked lists with random pointers correctly, programs that rely on copying complex data structures can break or cause bugs. For example, undo features, simulations, or games often need exact copies of states with random links. If cloning is shallow or incorrect, the new list might share parts with the old one, causing unexpected changes and errors. This concept helps keep data safe and independent when copied.

Where it fits

Before this, you should understand basic linked lists and pointers. After this, you can learn about graph cloning, deep vs shallow copy, and advanced data structure copying techniques.

Mental Model

Core Idea

Cloning a linked list with random pointers means making a new list where each node's next and random pointers correctly point to the new nodes, not the old ones.

Think of it like...

Imagine copying a group photo where each person is holding hands with the next person and also pointing randomly to a friend in the group. Cloning means making a new photo with new people holding hands and pointing exactly like the original, but no one is the same person.

Original List:  Node1 --next--> Node2 --next--> Node3 --next--> null
                 |             |             |
               random        random        random
                 |             |             |
               Node3        Node1         null

Cloned List:    Node1' --next--> Node2' --next--> Node3' --next--> null
                 |               |               |
               random          random          random
                 |               |               |
               Node3'         Node1'           null

Build-Up - 6 Steps

1

Foundation

Understand Basic Linked List Structure

Concept: Learn what a linked list is and how nodes connect with next pointers.

A linked list is a chain of nodes where each node has a value and a pointer to the next node. The last node points to null, meaning the end of the list. For example, Node1 points to Node2, Node2 points to Node3, and Node3 points to null.

Result

You can follow the chain from the first node to the last by following next pointers.

Understanding the simple chain of nodes is essential before adding complexity like random pointers.

2

Foundation

Introduce Random Pointer Concept

Concept: Each node has an extra pointer that can point to any node or null.

Besides the next pointer, each node has a random pointer. This pointer can point to any node in the list or be null. This means nodes have two ways to connect: the normal order and random jumps.

Result

You can visualize the list as a chain with extra random links crossing the chain.

Knowing that nodes have two pointers changes how you think about copying the list because you must copy both connections.

3

Intermediate

Naive Cloning with Hash Map

🤔Before reading on: do you think copying nodes one by one and using a map to fix random pointers is efficient or slow? Commit to your answer.

Concept: Use a map to remember original nodes and their copies to set random pointers correctly.

Step 1: Traverse the original list and create a copy of each node, storing pairs (original -> copy) in a map. Step 2: Traverse again to assign next and random pointers for copied nodes using the map. This ensures random pointers in the copy point to copied nodes, not original ones.

Result

A new list with correct next and random pointers is created, but it uses extra space for the map.

Using a map solves the problem of random pointers pointing anywhere, but it costs extra memory proportional to the list size.

4

Intermediate

Interleaving Nodes for Space Optimization

🤔Before reading on: can we clone the list without extra memory by mixing original and copied nodes? Guess yes or no.

Concept: Insert copied nodes right after original nodes to link them without extra space.

Step 1: For each original node, create a copy and insert it immediately after the original node. Step 2: Set the random pointer of the copied node by using the original node's random pointer's next node. Step 3: Separate the combined list into original and copied lists.

Result

The cloned list is created without extra map memory, using the original list structure cleverly.

Interleaving nodes cleverly uses the list itself to remember copies, saving memory and improving efficiency.

5

Advanced

Handling Edge Cases in Cloning

🤔Before reading on: do you think null random pointers or single-node lists cause problems? Commit your guess.

Concept: Consider cases like empty lists, single nodes, and null random pointers to avoid errors.

Check if the list is empty before cloning. For nodes with null random pointers, ensure the copied node's random pointer is also null. For single-node lists, the process is the same but simpler. Always verify pointers before accessing to avoid runtime errors.

Result

The cloning algorithm works safely for all list shapes and pointer values.

Handling edge cases prevents crashes and bugs in real-world usage where input can vary widely.

6

Expert

Time and Space Complexity Trade-offs

🤔Before reading on: which cloning method is faster or uses less memory? Predict the trade-offs.

Concept: Analyze the cloning methods for their speed and memory use to choose the best in practice.

The hash map method uses O(n) extra space but is straightforward. The interleaving method uses O(1) extra space but modifies the original list temporarily. Both methods run in O(n) time. Choosing depends on memory constraints and whether modifying the original list temporarily is allowed.

Result

You understand when to use each method based on resource limits and constraints.

Knowing trade-offs helps write efficient, safe code tailored to real project needs.

Under the Hood

The cloning process must create new nodes that replicate the original nodes' values and pointers. The challenge is that random pointers can point anywhere, so a direct copy of pointers would link back to original nodes. The hash map method stores a mapping from original to copied nodes to fix pointers after copying. The interleaving method temporarily inserts copied nodes between original nodes, so the copied node's random pointer can be set by looking at the original node's random pointer's next node, which is the copy. Finally, the combined list is split to restore the original and extract the copy.

Why designed this way?

The problem arises because random pointers break the simple linear structure of linked lists. Early solutions used extra memory to track copies. The interleaving method was designed to save memory by using the list structure itself, a clever trick discovered to optimize space without losing correctness. This design balances time and space efficiency.

Original List:  Node1 -> Node2 -> Node3 -> null

After Interleaving:
Node1 -> Node1' -> Node2 -> Node2' -> Node3 -> Node3' -> null

Random pointer fix:
Node1'.random = Node1.random ? Node1.random.next : null
Node2'.random = Node2.random ? Node2.random.next : null
Node3'.random = Node3.random ? Node3.random.next : null

Separate lists:
Original: Node1 -> Node2 -> Node3 -> null
Copy: Node1' -> Node2' -> Node3' -> null

Myth Busters - 3 Common Misconceptions

Quick: Does copying only next pointers also copy random pointers correctly? Commit yes or no.

Common Belief: Copying the next pointers alone is enough to clone the list.

Reality: Random pointers are independent and must be copied separately; otherwise, the clone's random pointers still point to original nodes.

Why it matters: If random pointers are not copied correctly, the cloned list is not independent and can cause bugs when modified.

Quick: Can we clone the list without any extra memory or modifying the original? Commit yes or no.

Common Belief: It's impossible to clone the list without extra memory or changing the original list.

Reality: The interleaving method clones the list in O(1) extra space by temporarily modifying the original list and then restoring it.

Why it matters: Knowing this allows writing memory-efficient code for large lists where extra memory is costly.

Quick: Does the order of setting next and random pointers during cloning matter? Commit yes or no.

Common Belief: You can set next and random pointers in any order during cloning.

Reality: The order matters; next pointers must be set first or handled carefully because random pointers rely on the structure to find copied nodes.

Why it matters: Incorrect order can cause null pointer errors or incorrect random pointer assignments.

Expert Zone

1

The interleaving method temporarily breaks the original list structure but restores it perfectly, which requires careful pointer manipulation to avoid data loss.

2

Random pointers can create cycles or complex graphs inside the list, so cloning must handle arbitrary pointer patterns without assumptions of acyclicity.

3

In concurrent environments, cloning must consider synchronization because the list might change during cloning, requiring locks or atomic operations.

When NOT to use

Avoid the interleaving method if the original list must remain untouched during cloning, such as in multi-threaded or real-time systems. Use the hash map method instead. Also, if memory is abundant and simplicity is preferred, the hash map method is better.

Production Patterns

In production, cloning with random pointers is used in undo-redo systems, game state snapshots, and complex object serialization. Often, the interleaving method is preferred for memory efficiency, but hash maps are used when code clarity and maintainability are priorities.

Connections

Graph Cloning

Builds-on

Cloning linked lists with random pointers is a special case of graph cloning where nodes have edges (pointers) to arbitrary nodes, helping understand more complex graph copy problems.

Deep vs Shallow Copy

Related concept

This topic illustrates the difference between shallow copy (copying references) and deep copy (copying objects and their connections), a fundamental concept in programming.

Memory Management in Operating Systems

Analogy in different field

Just like cloning linked lists requires careful pointer handling to avoid shared references, memory management involves copying and isolating memory spaces to prevent interference, showing similar principles across fields.

Common Pitfalls

#1 Not copying random pointers leads to incorrect clones.

Wrong approach:

function cloneList(head) {
if (!head) return null;
let newHead = new Node(head.val);
let current = head.next;
let copyCurrent = newHead;
while (current) {
copyCurrent.next = new Node(current.val);
copyCurrent = copyCurrent.next;
current = current.next;
}
return newHead;
}

Correct approach:

function cloneList(head) {
if (!head) return null;
const map = new Map();
let current = head;
while (current) {
map.set(current, new Node(current.val));
current = current.next;
}
current = head;
while (current) {
map.get(current).next = map.get(current.next) || null;
map.get(current).random = map.get(current.random) || null;
current = current.next;
}
return map.get(head);
}

Root cause:

Misunderstanding that random pointers need separate copying and fixing after node creation.

#2 Modifying original list permanently during interleaving.

Wrong approach:

function cloneList(head) {
if (!head) return null;
let current = head;
while (current) {
let copy = new Node(current.val);
copy.next = current.next;
current.next = copy;
current = copy.next;
}
// Forgot to restore original list
return head.next;
}

Correct approach:

function cloneList(head) {
if (!head) return null;
let current = head;
while (current) {
let copy = new Node(current.val);
copy.next = current.next;
current.next = copy;
current = copy.next;
}
current = head;
while (current) {
current.next.random = current.random ? current.random.next : null;
current = current.next.next;
}
current = head;
let pseudoHead = new Node(0);
let copyCurrent = pseudoHead;
while (current) {
let copy = current.next;
copyCurrent.next = copy;
copyCurrent = copy;
current.next = copy.next;
current = current.next;
}
return pseudoHead.next;
}

Root cause:

Forgetting to separate the copied nodes from the original list after interleaving.

#3 Accessing random pointer without null check causes errors.

Wrong approach:

copyNode.random = originalNode.random.next;

Correct approach:

copyNode.random = originalNode.random ? originalNode.random.next : null;

Root cause:

Not handling cases where random pointer is null leads to runtime exceptions.

Key Takeaways

Cloning a linked list with random pointers requires copying both next and random pointers to create an independent list.

Using a hash map is a simple way to clone but uses extra memory proportional to the list size.

The interleaving method cleverly inserts copied nodes between original nodes to clone with constant extra space.

Handling edge cases like null pointers and empty lists is essential for robust cloning.

Understanding the trade-offs between time and space helps choose the best cloning method for your needs.

Practice

1. What is the main challenge when cloning a linked list with a random pointer?

easy

A. Reversing the linked list before cloning

B. Copying the data values of each node

C. Maintaining the correct random pointer connections in the cloned list

D. Sorting the linked list nodes

Solution

1. Step 1: Understand the structure of the linked list

   The linked list has two pointers: next and random. The random pointer can point to any node or null.

2. Step 2: Identify the cloning challenge

   While copying nodes is straightforward, correctly assigning random pointers in the cloned list is tricky because they may point to nodes not yet cloned.

3. Final Answer:

   Maintaining the correct random pointer connections in the cloned list -> Option C

4. Quick Check:

   Random pointer cloning = main challenge [OK]

Hint: Focus on copying random pointers correctly [OK]

Common Mistakes:

• Ignoring random pointers during cloning
• Assuming random pointers are always null
• Copying only next pointers

2. Which TypeScript syntax correctly declares a node with a random pointer in a linked list?

easy

A. class Node { val: number; next: Node | null; random: Node | null; constructor(val?: number) { this.val = val ?? 0; this.next = null; this.random = null; } }

B. class Node { val: number; next: Node; random: Node; constructor(val: number) { this.val = val; this.next = null; this.random = null; } }

C. interface Node { val: number; next: Node; random: Node; }

D. type Node = { val: number; next?: Node; random?: Node; };

Solution

1. Step 1: Check for nullable pointers

   Both next and random pointers can be null, so their types must allow null.

2. Step 2: Verify constructor and property declarations

   class Node { val: number; next: Node | null; random: Node | null; constructor(val?: number) { this.val = val ?? 0; this.next = null; this.random = null; } } correctly uses 'Node | null' and initializes properties properly with optional val.

3. Final Answer:

   Option A correctly declares nullable next and random pointers with proper constructor -> Option A

4. Quick Check:

   Nullable pointers + constructor = class Node { val: number; next: Node | null; random: Node | null; constructor(val?: number) { this.val = val ?? 0; this.next = null; this.random = null; } } [OK]

Hint: Use 'Node | null' for nullable pointers in TypeScript [OK]

Common Mistakes:

• Not allowing null for next or random
• Using interface without constructor
• Missing property initializations

3. What is the output of the following TypeScript code snippet that clones a linked list with random pointers?

class Node {
  val: number;
  next: Node | null;
  random: Node | null;
  constructor(val?: number) {
    this.val = val ?? 0;
    this.next = null;
    this.random = null;
  }
}

function cloneList(head: Node | null): Node | null {
  if (!head) return null;
  let curr = head;
  while (curr) {
    const copy = new 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;
  }
  curr = head;
  const pseudoHead = new Node(0);
  let copyCurr = pseudoHead;
  while (curr) {
    copyCurr.next = curr.next;
    curr.next = curr.next!.next;
    copyCurr = copyCurr.next;
    curr = curr.next;
  }
  return pseudoHead.next;
}

// Original list: 1 -> 2 -> null
// Node 1 random points to Node 2
// Node 2 random points to Node 1

const node1 = new Node(1);
const node2 = new Node(2);
node1.next = node2;
node1.random = node2;
node2.random = node1;

const clonedHead = cloneList(node1);

console.log(clonedHead!.val);
console.log(clonedHead!.random!.val);
console.log(clonedHead!.next!.val);
console.log(clonedHead!.next!.random!.val);

medium

A. 1 2 2 1

B. 1 1 2 2

C. 2 1 1 2

D. 1 2 1 2

Solution

1. Step 1: Understand cloning steps

   The code interleaves cloned nodes, assigns random pointers, then separates the cloned list.

2. Step 2: Trace output values

   clonedHead.val = 1; clonedHead.random.val = 2; clonedHead.next.val = 2; clonedHead.next.random.val = 1.

3. Final Answer:

   1 2 2 1 -> Option A

4. Quick Check:

   Cloned values and randoms match original pattern [OK]

Hint: Interleave nodes, assign randoms, then separate [OK]

Common Mistakes:

• Not updating random pointers correctly
• Mixing original and cloned nodes in output
• Confusing next and random values

4. Identify the bug in this TypeScript function that attempts to clone a linked list with random pointers:

function cloneList(head: Node | null): Node | null {
  if (!head) return null;
  let curr = head;
  while (curr) {
    const copy = new Node(curr.val);
    copy.next = curr.next;
    curr.next = copy;
    curr = curr.next;
  }
  curr = head;
  while (curr) {
    if (curr.random) curr.next!.random = curr.random.next;
    curr = curr.next!.next;
  }
  curr = head;
  const pseudoHead = new Node(0);
  let copyCurr = pseudoHead;
  while (curr) {
    copyCurr.next = curr.next;
    curr.next = curr.next!.next;
    copyCurr = copyCurr.next;
    curr = curr.next;
  }
  return pseudoHead.next;
}

medium

A. Random pointers are not assigned at all

B. In the first while loop, curr is updated incorrectly causing an infinite loop

C. The cloned list is not separated from the original list

D. The function does not handle empty lists

Solution

1. Step 1: Analyze the first while loop

   Inside the loop, curr is updated as curr = curr.next, but curr.next is the cloned node, so curr never moves past cloned nodes, causing infinite loop.

2. Step 2: Correct the pointer update

   It should be curr = copy.next to move to the next original node.

3. Final Answer:

   In the first while loop, curr is updated incorrectly causing an infinite loop -> Option B

4. Quick Check:

   Incorrect curr update = infinite loop [OK]

Hint: Update curr to next original node, not cloned node [OK]

Common Mistakes:

• Updating curr to curr.next instead of curr.next.next
• Skipping random pointer assignment
• Not separating cloned list

5. Given a linked list with random pointers, how would you modify the cloning algorithm to handle the case where some random pointers point to null and others form cycles? Choose the best approach.

hard

A. Ignore random pointers that are null and only clone non-null random pointers

B. Reverse the linked list before cloning to handle cycles

C. Clone nodes and assign random pointers in a single pass without extra space

D. Use a hash map to store original to cloned node mappings and assign random pointers after cloning all nodes

Solution

1. Step 1: Understand random pointer complexities

   Random pointers can be null or form cycles, so direct assignment during cloning is unsafe.

2. Step 2: Use a hash map for safe cloning

   Mapping original nodes to cloned nodes allows assigning random pointers correctly after all nodes are cloned, handling nulls and cycles safely.

3. Final Answer:

   Use a hash map to store original to cloned node mappings and assign random pointers after cloning all nodes -> Option D

4. Quick Check:

   Hash map handles nulls and cycles safely [OK]

Hint: Use hash map to track clones before assigning randoms [OK]

Common Mistakes:

• Ignoring null random pointers
• Trying to assign randoms in one pass without map
• Reversing list unnecessarily