Clone Linked List with Random Pointer in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of cloning a linked list with random pointers

What is the printed output of the cloned linked list's values and their random pointers after running the given code?

DSA Javascript

class Node {
  constructor(val, next = null, random = null) {
    this.val = val;
    this.next = next;
    this.random = random;
  }
}

function cloneLinkedList(head) {
  if (!head) return null;

  let curr = head;
  // Step 1: Insert cloned nodes
  while (curr) {
    let newNode = new Node(curr.val);
    newNode.next = curr.next;
    curr.next = newNode;
    curr = newNode.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 cloned list
  curr = head;
  let cloneHead = head.next;
  while (curr) {
    let clone = curr.next;
    curr.next = clone.next;
    clone.next = clone.next ? clone.next.next : null;
    curr = curr.next;
  }

  return cloneHead;
}

// Original list setup
const node1 = new Node(1);
const node2 = new Node(2);
const node3 = new Node(3);
node1.next = node2;
node2.next = node3;
node1.random = node3;
node2.random = node1;
node3.random = node2;

const clonedHead = cloneLinkedList(node1);

// Print cloned list values and their random values
let output = [];
let temp = clonedHead;
while (temp) {
  output.push({ val: temp.val, random: temp.random ? temp.random.val : null });
  temp = temp.next;
}
console.log(output);

A [{"val":1,"random":3},{"val":2,"random":1},{"val":3,"random":2}]

B [{"val":1,"random":1},{"val":2,"random":2},{"val":3,"random":3}]

C [{"val":1,"random":null},{"val":2,"random":null},{"val":3,"random":null}]

D [{"val":1,"random":2},{"val":2,"random":3},{"val":3,"random":1}]

💡 Hint

Focus on how the random pointers are assigned in the cloned list using the original nodes' random pointers.

The cloning process creates new nodes interleaved with original nodes. The random pointer of each cloned node is set to the next node of the original node's random pointer. This preserves the random links correctly in the cloned list.

🧠 Conceptual

intermediate

Understanding the purpose of interleaving nodes in cloning

Why do we insert cloned nodes between original nodes in the cloning process of a linked list with random pointers?

A To remove duplicate nodes from the original list

B To sort the linked list nodes in ascending order

C To easily assign random pointers of cloned nodes using original nodes' random pointers without extra space

D To reverse the linked list while cloning

💡 Hint

Think about how the random pointers are linked between original and cloned nodes.

Interleaving cloned nodes allows direct access to the cloned node corresponding to any original node's random pointer by using originalNode.random.next. This avoids using extra memory like hash maps.

🔧 Debug

advanced

Identify the bug in this cloning code snippet

What error or issue will occur when running this code snippet for cloning a linked list with random pointers?

DSA Javascript

function cloneLinkedList(head) {
  if (!head) return null;
  let curr = head;
  while (curr) {
    let newNode = new Node(curr.val);
    newNode.next = curr.next;
    curr.next = newNode;
    curr = curr.next;
  }
  // Missing step to assign random pointers
  curr = head;
  let cloneHead = head.next;
  while (curr) {
    let clone = curr.next;
    curr.next = clone.next;
    clone.next = clone.next ? clone.next.next : null;
    curr = curr.next;
  }
  return cloneHead;
}

A The cloned list's random pointers will all be null, losing original random links

B The code will throw a TypeError due to accessing undefined properties

C The cloned list will have cycles causing infinite loops

D The original list will be reversed after cloning

💡 Hint

Check if the random pointers are assigned in the cloned nodes.

The code misses the step where cloned nodes' random pointers are assigned. Without this, all cloned nodes have random set to null.

❓ Predict Output

advanced

Output after cloning a single-node list with self-random pointer

What is the output of the cloned list when the original list has one node whose random pointer points to itself?

DSA Javascript

class Node {
  constructor(val, next = null, random = null) {
    this.val = val;
    this.next = next;
    this.random = random;
  }
}

function cloneLinkedList(head) {
  if (!head) return null;
  let curr = head;
  while (curr) {
    let newNode = new Node(curr.val);
    newNode.next = curr.next;
    curr.next = newNode;
    curr = newNode.next;
  }
  curr = head;
  while (curr) {
    if (curr.random) {
      curr.next.random = curr.random.next;
    }
    curr = curr.next.next;
  }
  curr = head;
  let cloneHead = head.next;
  while (curr) {
    let clone = curr.next;
    curr.next = clone.next;
    clone.next = clone.next ? clone.next.next : null;
    curr = curr.next;
  }
  return cloneHead;
}

const node = new Node(10);
node.random = node;
const cloned = cloneLinkedList(node);

let output = [];
let temp = cloned;
while (temp) {
  output.push({ val: temp.val, random: temp.random ? temp.random.val : null });
  temp = temp.next;
}
console.log(output);

A [{"val":10,"random":undefined}]

B [{"val":10,"random":10}]

C []

D [{"val":10,"random":null}]

💡 Hint

Check how the random pointer of the single node is cloned.

The cloned node's random pointer points to itself because original node's random points to itself, so cloned node's random is original.random.next which is cloned node itself.

🧠 Conceptual

expert

Time and space complexity of cloning linked list with random pointer

What are the time and space complexities of the optimal algorithm that clones a linked list with random pointers by interleaving cloned nodes?

A Time: O(log n), Space: O(1)

B Time: O(n^2), Space: O(n)

C Time: O(n), Space: O(n)

D Time: O(n), Space: O(1)

💡 Hint

Consider how many times the list is traversed and if extra data structures are used.

The interleaving method traverses the list a constant number of times and uses no extra space besides the cloned nodes, so time is linear and space is constant.

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