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

Concept Flow - Clone Linked List with Random Pointer

Start at head

↓

Create new node after each original node

↓

Assign random pointers for new nodes

↓

Separate original and cloned lists

↓

Return head of cloned list

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

Execution Sample

DSA Javascript

function cloneList(head) {
  let curr = head;
  while (curr) {
    let newNode = { val: curr.val, next: curr.next, random: null };
    curr.next = newNode;
    curr = newNode.next;
  }
  // ...

This code clones nodes by inserting new nodes after each original node.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Insert clone after node 1	1 -> 2 -> 3 -> null	1.next = newNode(1')	1 -> 1' -> 2 -> 3 -> null
2	Insert clone after node 2	1 -> 1' -> 2 -> 3 -> null	2.next = newNode(2')	1 -> 1' -> 2 -> 2' -> 3 -> null
3	Insert clone after node 3	1 -> 1' -> 2 -> 2' -> 3 -> null	3.next = newNode(3')	1 -> 1' -> 2 -> 2' -> 3 -> 3' -> null
4	Assign random for 1'	Full list as above	1'.random = 3'	1 -> 1'(random->3') -> 2 -> 2' -> 3 -> 3' -> null
5	Assign random for 2'	Full list as above	2'.random = 1'	1 -> 1'(random->3') -> 2 -> 2'(random->1') -> 3 -> 3' -> null
6	Assign random for 3'	Full list as above	3'.random = 2'	1 -> 1'(random->3') -> 2 -> 2'(random->1') -> 3 -> 3'(random->2') -> null
7	Separate original and cloned lists	Combined list as above	Restore original next pointers, set clone next pointers	Original: 1 -> 2 -> 3 -> null Clone: 1' -> 2' -> 3' -> null
8	Return cloned list head	Clone list: 1' -> 2' -> 3' -> null	Return pointer to 1'	Cloned list ready

💡 All nodes cloned and random pointers assigned; original list restored.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 7	Final
curr	head (1)	2	3	null	null	null
newNode	null	1'	2'	3'	null	null
head	1	1	1	1	1	1
cloneHead	null	null	null	null	1'	1'

Key Moments - 3 Insights

Why do we insert cloned nodes immediately after original nodes?

Inserting clones after originals (see steps 1-3 in execution_table) allows easy access to the clone when setting random pointers without extra space.

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

We use the original node's random pointer to find the target, then assign the clone's random to the next node of that target (steps 4-6).

How do we separate the combined list back into original and cloned lists?

We restore original nodes' next pointers and set cloned nodes' next pointers by skipping alternate nodes (step 7).

Visual Quiz - 3 Questions

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

A Node 2'

B Node 3'

C Node 1

D Null

💡 Hint

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

At which step do we restore the original list's next pointers?

A Step 7

B Step 5

C Step 3

D Step 8

💡 Hint

Look for 'Restore original next pointers' in the 'Pointer Changes' column.

If we skip inserting cloned nodes after originals, how would the random pointer assignment change?

A Random pointers would be null by default.

B We could assign random pointers directly without extra steps.

C We would need extra space like a map to track clones.

D Random pointers would point to original nodes.

💡 Hint

Think about how clones are found during random pointer assignment in steps 4-6.

Concept Snapshot

Clone Linked List with Random Pointer:
1. Insert cloned node after each original node.
2. Assign cloned nodes' random pointers using original nodes' random.next.
3. Separate the combined list into original and cloned lists.
4. Return cloned list head.
This method avoids extra space by interleaving clones.

Full Transcript

To clone a linked list with random pointers, we first insert a cloned node after each original node. This interleaving helps us assign the random pointers of cloned nodes by referencing the original nodes' random pointers and their next nodes. After setting all random pointers, we separate the combined list into the original and cloned lists by restoring the original next pointers and setting the cloned next pointers. Finally, we return the head of the cloned list. This approach avoids using extra space like hash maps.

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 values of the nodes only

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

D. Sorting the linked list nodes before cloning

Solution

1. Step 1: Understand the linked list structure

   A linked list with random pointers has two references per node: next and random. Cloning must preserve both.

2. Step 2: Identify the cloning challenge

   While copying next pointers is straightforward, random pointers can point anywhere, so they must be carefully mapped to cloned nodes.

3. Final Answer:

   Maintaining the correct random pointer references 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 follow next pointers
• Copying only node values without pointers

2. Which of the following JavaScript code snippets correctly creates a new node with value `val` and initializes its `next` and `random` pointers to null?

easy

A. function Node(val) { this.value = val; this.next = null; this.random = null; }

B. function Node(val) { this.val = val; this.next = val; this.random = val; }

C. function Node(val) { this.val = val; this.next = undefined; this.random = undefined; }

D. function Node(val) { this.val = val; this.next = null; this.random = null; }

Solution

1. Step 1: Check property names and initialization

   The node should have properties named val, next, and random. Both next and random should start as null.

2. Step 2: Verify code correctness

   function Node(val) { this.val = val; this.next = null; this.random = null; } correctly assigns val and sets next and random to null. Others either use wrong property names or incorrect initial values.

3. Final Answer:

   function Node(val) { this.val = val; this.next = null; this.random = null; } -> Option D

4. Quick Check:

   Correct node constructor = function Node(val) { this.val = val; this.next = null; this.random = null; } [OK]

Hint: Use null for uninitialized pointers in node constructor [OK]

Common Mistakes:

• Using wrong property names like value instead of val
• Initializing pointers with val instead of null
• Using undefined instead of null for pointers

3. Given the following code snippet to clone a linked list with random pointers, what will be the output of the console.log after cloning?

function Node(val) {
  this.val = val;
  this.next = null;
  this.random = null;
}

// Original list: 1 -> 2 -> null
const node1 = new Node(1);
const node2 = new Node(2);
node1.next = node2;
node1.random = node2;
node2.random = node2;

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

const clonedHead = cloneList(node1);
console.log(clonedHead.val, clonedHead.next.val, clonedHead.random.val);

medium

A. 1 2 1

B. 1 2 2

C. 1 1 2

D. 2 1 2

Solution

1. Step 1: Understand the original list structure

   Node1.val=1, Node2.val=2; node1.next=node2; node1.random=node2; node2.random=node2.

2. Step 2: Trace cloning and pointer assignments

   Cloned node1 has val=1, next points to cloned node2 (val=2), random points to cloned node2 (val=2).

3. Final Answer:

   1 2 2 -> Option B

4. Quick Check:

   Cloned list values = 1 2 2 [OK]

Hint: Map original nodes to clones to fix random pointers [OK]

Common Mistakes:

• Confusing random pointer values
• Not mapping random pointers correctly
• Printing original node values instead of cloned

4. The following code attempts to clone a linked list with random pointers but has a bug. What is the bug?

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

medium

A. Random pointers are assigned to original nodes instead of cloned nodes

B. Next pointers are not assigned at all

C. Map is not used to store cloned nodes

D. Function returns null always

Solution

1. Step 1: Analyze random pointer assignment

   map.get(curr).random = curr.random assigns original node's random pointer, not cloned node's.

2. Step 2: Identify correct assignment

   It should be map.get(curr).random = map.get(curr.random) to assign cloned random pointer.

3. Final Answer:

   Random pointers are assigned to original nodes instead of cloned nodes -> Option A

4. Quick Check:

   Random pointer assignment bug = Random pointers are assigned to original nodes instead of cloned nodes [OK]

Hint: Always map random pointers to cloned nodes [OK]

Common Mistakes:

• Assigning random pointers directly from original nodes
• Forgetting to map next pointers
• Not initializing map before use

5. You want to clone a linked list with random pointers without using extra space (no hash maps). Which approach correctly describes the process?

hard

A. Interleave cloned nodes between original nodes, assign random pointers, then separate the lists

B. Create a new list by copying values only, ignoring random pointers

C. Use recursion to clone nodes and random pointers simultaneously

D. Reverse the original list, clone nodes, then reverse back

Solution

1. Step 1: Interleave cloned nodes

   Insert cloned nodes right after each original node, so list looks like original1 -> clone1 -> original2 -> clone2 -> ...

2. Step 2: Assign random pointers and separate lists

   Set clone.random = original.random.next, then detach cloned nodes to form the cloned list.

3. Final Answer:

   Interleave cloned nodes between original nodes, assign random pointers, then separate the lists -> Option A

4. Quick Check:

   Interleaving method = Interleave cloned nodes between original nodes, assign random pointers, then separate the lists [OK]

Hint: Interleave clones to avoid extra space [OK]

Common Mistakes:

• Ignoring random pointers in cloning
• Using extra space despite requirement
• Incorrectly separating the cloned list