Clone Linked List with Random Pointer in DSA Javascript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to create a new node with the same value as the current node.

DSA Javascript

let newNode = new Node(current.val[1]);

Drag options to blanks, or click blank then click option'

A{}

B[]

C()

D;

Attempts:

3 left

💡 Hint

Common Mistakes

Forgetting parentheses when calling the constructor.

Using brackets or braces instead of parentheses.

The Node constructor requires parentheses to pass the value argument.

2fill in blank

medium

Complete the code to link the new node right after the current node.

DSA Javascript

current.next = [1];

Drag options to blanks, or click blank then click option'

Acurrent

Bnull

Ccurrent.next

DnewNode

Attempts:

3 left

💡 Hint

Common Mistakes

Assigning current.next to current itself causes a cycle.

Assigning current.next to null breaks the list.

We want to insert the new node after current, so current.next should point to newNode.

3fill in blank

hard

Fix the error in setting the random pointer of the copied node.

DSA Javascript

current.next.random = current.random[1];

Drag options to blanks, or click blank then click option'

A.random

B.next

C.val

D.prev

Attempts:

3 left

💡 Hint

Common Mistakes

Setting random to current.random instead of current.random.next.

Using .random.random which is incorrect.

The copied node's random pointer should point to the copied node of current.random, which is current.random.next.

4fill in blank

hard

Fill both blanks to restore the original list and extract the copied list.

DSA Javascript

original.next = original.next[1];
copied.next = copied.next[2];

Drag options to blanks, or click blank then click option'

A.next

B.random

C.prev

D.val

Attempts:

3 left

💡 Hint

Common Mistakes

Using .random instead of .next breaks the list.

Assigning empty string causes syntax errors.

To restore the original list and copied list, we skip alternate nodes by assigning next pointers to next.next.

5fill in blank

hard

Fill all three blanks to complete the function that clones the linked list with random pointers.

DSA Javascript

function copyRandomList(head) {
  if (!head) return null;
  let current = head;
  while (current) {
    let newNode = new Node(current.val[1]);
    newNode.next = current.next;
    current.next = newNode;
    current = newNode.next;
  }
  current = head;
  while (current) {
    if (current.random) {
      current.next.random = current.random[2];
    }
    current = current.next.next;
  }
  let original = head;
  let copy = head.next;
  let copiedHead = copy;
  while (original) {
    original.next = original.next[3];
    copy.next = copy.next ? copy.next.next : null;
    original = original.next;
    copy = copy.next;
  }
  return copiedHead;
}

Drag options to blanks, or click blank then click option'

A()

B.next

C.prev

D.random

Attempts:

3 left

💡 Hint

Common Mistakes

Missing parentheses in Node constructor.

Setting random pointer incorrectly.

Not restoring original list properly.

The blanks correspond to calling the Node constructor with parentheses, accessing current.random.next for the copied random pointer, and restoring original.next to original.next.next.

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