Clone Linked List with Random Pointer in DSA Typescript - 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 Typescript

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

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

  // Step 1: Insert cloned nodes
  let curr: Node | null = head;
  while (curr) {
    const newNode = new Node(curr.val, curr.next, null);
    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 lists
  curr = head;
  const dummy = new Node(0);
  let copyCurr = dummy;
  while (curr) {
    copyCurr.next = curr.next;
    curr.next = curr.next!.next;
    curr = curr.next;
    copyCurr = copyCurr.next!;
  }

  return dummy.next;
}

// Create original list
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 random values
let temp = clonedHead;
const result: string[] = [];
while (temp) {
  const randomVal = temp.random ? temp.random.val : 'null';
  result.push(`${temp.val}->random:${randomVal}`);
  temp = temp.next;
}
console.log(result.join(' -> '));

A "1->random:1 -> 2->random:2 -> 3->random:3"

B "1->random:2 -> 2->random:3 -> 3->random:1"

C "1->random:null -> 2->random:null -> 3->random:null"

D "1->random:3 -> 2->random:1 -> 3->random:2"

💡 Hint

Trace the cloning steps carefully, especially how random pointers are assigned.

The cloned list nodes have the same values as original nodes. The random pointers in the clone point to the cloned nodes corresponding to the original random targets. So node 1's random points to node 3, node 2's random points to node 1, and node 3's random points to node 2.

🧠 Conceptual

intermediate

Understanding the purpose of interleaving cloned nodes

Why do we insert cloned nodes immediately after their original nodes in the linked list during cloning with random pointers?

A To easily assign random pointers of cloned nodes by using original nodes' random pointers.

B To sort the linked list nodes by their values.

C To reduce the memory usage by sharing nodes between original and clone.

D To reverse the linked list while cloning.

💡 Hint

Think about how random pointers can be assigned without extra space.

By placing cloned nodes right after original nodes, we can access the clone of any node's random pointer by looking at original.random.next. This avoids using extra space like hash maps.

🔧 Debug

advanced

Identify the bug causing incorrect random pointers in cloned list

Given the following code snippet for cloning a linked list with random pointers, what is the bug causing cloned nodes to have incorrect random pointers?

DSA Typescript

function cloneRandomList(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;
    }
    curr = curr.next!.next;
  }
  curr = head;
  const dummy = new Node(0);
  let copyCurr = dummy;
  while (curr) {
    copyCurr.next = curr.next;
    curr.next = curr.next!.next;
    curr = curr.next;
    copyCurr = copyCurr.next!;
  }
  return dummy.next;
}

A The function does not handle empty list input.

B The random pointer assignment should be curr.next!.random = curr.random.next instead of curr.random.

C The next pointers of cloned nodes are not set properly during separation.

D The cloned nodes are not inserted correctly after original nodes.

💡 Hint

Check how random pointers of cloned nodes are assigned.

The cloned node's random pointer must point to the clone of the original node's random target, which is curr.random.next, not curr.random itself.

❓ Predict Output

advanced

Output after cloning a linked list with some null random pointers

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

DSA Typescript

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

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

const n1 = new Node(10);
const n2 = new Node(20);
const n3 = new Node(30);
const n4 = new Node(40);
n1.next = n2;
n2.next = n3;
n3.next = n4;
n1.random = null;
n2.random = n4;
n3.random = null;
n4.random = n2;

const cloned = cloneList(n1);

let temp = cloned;
const output: string[] = [];
while (temp) {
  const r = temp.random ? temp.random.val : 'null';
  output.push(`${temp.val}->random:${r}`);
  temp = temp.next;
}
console.log(output.join(' -> '));

A "10->random:null -> 20->random:40 -> 30->random:null -> 40->random:20"

B "10->random:10 -> 20->random:20 -> 30->random:30 -> 40->random:40"

C "10->random:20 -> 20->random:30 -> 30->random:40 -> 40->random:null"

D "10->random:null -> 20->random:null -> 30->random:null -> 40->random:null"

💡 Hint

Check which original nodes have null random pointers and how they map in the clone.

The cloned list preserves the original random pointer structure, including nulls. So nodes with null random remain null in clone; others point to the cloned target nodes.

🚀 Application

expert

Time complexity of cloning a linked list with random pointers

What is the overall time complexity of cloning a linked list with random pointers using the interleaving method shown in the code examples?

A O(n^2), due to nested loops for random pointer assignment

B O(log n), because of divide and conquer approach

C O(n), where n is the number of nodes in the list

D O(1), constant time regardless of list size

💡 Hint

Consider how many times each node is visited during cloning.

The algorithm visits each node a constant number of times: once to insert clones, once to assign random pointers, and once to separate lists, resulting in O(n) time.

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