Clone Linked List with Random Pointer in DSA Typescript - Execution Trace

Concept Flow - Clone Linked List with Random Pointer

Start with original list

↓

Step 1: Insert cloned nodes

↓

Step 2: Assign random pointers to clones

↓

Step 3: Separate cloned list from original

↓

Return cloned list head

We first insert cloned nodes next to original nodes, then set their random pointers, and finally separate the cloned list.

Execution Sample

DSA Typescript

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

function cloneRandomList(head: Node | null): Node | null {
  if (!head) return null;

  // Step 1: Insert cloned nodes
  let curr = head;
  while (curr) {
    const clone = new Node(curr.val, curr.next, null);
    curr.next = clone;
    curr = clone.next;
  }

  // Step 2: Assign random pointers
  curr = head;
  while (curr) {
    if (curr.random) {
      curr.next!.random = curr.random.next;
    }
    curr = curr.next!.next;
  }

  // Step 3: Separate lists
  curr = head;
  const cloneHead = head.next;
  while (curr) {
    const clone = curr.next!;
    curr.next = clone.next;
    clone.next = clone.next ? clone.next.next : null;
    curr = curr.next;
  }

  return cloneHead;
}

This code clones a linked list with random pointers by interleaving cloned nodes, setting random pointers, and then separating the cloned list.

Execution Table

Step	Operation	Current Node	Pointer Changes	Visual State
1	Insert clone after original node 1	Node 1	Node 1.next = Clone 1 (val=1)	1 -> 1' -> 2 -> 3 -> null (randoms unchanged)
2	Insert clone after original node 2	Node 2	Node 2.next = Clone 2 (val=2)	1 -> 1' -> 2 -> 2' -> 3 -> null
3	Insert clone after original node 3	Node 3	Node 3.next = Clone 3 (val=3)	1 -> 1' -> 2 -> 2' -> 3 -> 3' -> null
4	Assign random pointer for Clone 1	Node 1	Clone 1.random = Node 1.random.next (Clone of Node 3)	Clone 1.random -> 3'
5	Assign random pointer for Clone 2	Node 2	Clone 2.random = Node 2.random.next (Clone of Node 1)	Clone 2.random -> 1'
6	Assign random pointer for Clone 3	Node 3	Clone 3.random = Node 3.random.next (Clone of Node 2)	Clone 3.random -> 2'
7	Separate clone list from original at Node 1	Node 1	Node 1.next = Node 2, Clone 1.next = Clone 2	Original: 1 -> 2 -> 3 -> null Clone: 1' -> 2' -> 3' -> null
8	Separate clone list from original at Node 2	Node 2	Node 2.next = Node 3, Clone 2.next = Clone 3	Original: 1 -> 2 -> 3 -> null Clone: 1' -> 2' -> 3' -> null
9	Separate clone list from original at Node 3	Node 3	Node 3.next = null, Clone 3.next = null	Original: 1 -> 2 -> 3 -> null Clone: 1' -> 2' -> 3' -> null
10	Return cloned list head	Clone 1	Return pointer to Clone 1	Cloned list head at 1'
11	Exit	null	All nodes processed and lists separated	Process complete

💡 All original nodes processed, cloned list separated and returned

Variable Tracker

Variable	Start	After Step 3	After Step 6	After Step 9	Final
curr	Node 1	null (end of insertion)	null (end of random assignment)	null (end of separation)	null
head	Node 1	Node 1	Node 1	Node 1	Node 1
cloneHead	null	null	Node 1'	Node 1'	Node 1'
List Size	3 nodes	6 nodes (original + clones interleaved)	6 nodes	3 nodes original + 3 nodes clone separated	3 nodes clone returned

Key Moments - 3 Insights

Why do we insert cloned nodes immediately after original nodes instead of creating a separate list first?

Inserting clones next to originals allows easy access to the clone of any node via original.next, which simplifies setting random pointers as shown in steps 4-6 of the execution_table.

How do we correctly assign the random pointer of a cloned node?

Since each clone is right after its original, the clone's random pointer is set to original.random.next (the clone of the original's random), as shown in steps 4-6.

Why do we need to separate the cloned list from the original at the end?

Because clones were inserted inside the original list, we must restore the original list's next pointers and extract the clones to form a separate cloned list, as done in steps 7-9.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the random pointer of Clone 1 set to?

A Clone of Node 3

B Node 1

C Node 3

D null

💡 Hint

Check the 'Pointer Changes' and 'Visual State' columns at step 4 in execution_table.

At which step does the original list get restored to its initial form?

A Step 3

B Step 6

C Step 9

D Step 11

💡 Hint

Look at the 'Operation' and 'Pointer Changes' columns in execution_table for separation steps.

If we skipped inserting cloned nodes next to originals, how would the random pointer assignment change?

A We could assign random pointers directly without extra steps

B We would need a map from original nodes to clones to assign random pointers

C Random pointers would be null by default

D Random pointers would point to original nodes

💡 Hint

Think about how random pointers are assigned in steps 4-6 and what helps us find the clone of a random node.

Concept Snapshot

Clone Linked List with Random Pointer:
1. Insert cloned nodes after originals.
2. Set clone.random = original.random.next.
3. Separate cloned list from original.
This avoids extra space by interleaving clones.
Return cloned list head.

Full Transcript

To clone a linked list with random pointers, we first insert cloned nodes immediately after each original node. This interleaving allows us to assign the random pointers of cloned nodes by referencing the original node's random pointer's next node, which is the clone. After setting all random pointers, we separate the cloned nodes into a new list, restoring the original list to its initial form. This method efficiently clones the list without extra space for mapping nodes.

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