Clone Linked List with Random Pointer in DSA Typescript - Build from Scratch

Clone Linked List with Random Pointer

📖 Scenario: You have a special linked list where each node has two pointers: one points to the next node, and another points randomly to any node in the list or null. This is like a group of friends where each friend points to the next friend in line and also has a secret friend they point to randomly.

🎯 Goal: You will build a program to create a perfect copy of this special linked list. The copy should have new nodes but keep the same next and random connections as the original.

📋 What You'll Learn

Create a Node class with val, next, and random properties

Build the original linked list with exact nodes and connections

Write a function copyRandomList that clones the list with correct next and random pointers

Print the cloned list nodes showing val and the val of their random pointers

💡 Why This Matters

🌍 Real World

Cloning complex linked data structures is useful in applications like undo-redo systems, copying game states, or duplicating complex object graphs.

💼 Career

Understanding how to clone linked lists with random pointers is a common interview question and tests your ability to handle pointers and references carefully.

1

Create the Node class and build the original linked list

Create a class called Node with a constructor that takes val: number and initializes next and random to null. Then create four nodes with values 7, 13, 11, and 10. Link them using next pointers in this order: 7 -> 13 -> 11 -> 10 -> null.

DSA Typescript

// Define Node class and create nodes 7, 13, 11, 10 linked by next pointers
// Your code here

Hint

Think of each node as a box with a number and two empty arrows. First, create the boxes, then connect their next arrows in order.

2

Set the random pointers for the original list

Set the random pointers for the nodes as follows: node1.random = null, node2.random = node1, node3.random = node4, and node4.random = node2.

DSA Typescript

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

const node1 = new Node(7);
const node2 = new Node(13);
const node3 = new Node(11);
const node4 = new Node(10);

node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = null;

// Set random pointers as described
// Your code here

Hint

Imagine each friend pointing to their secret friend. Set these secret friend arrows carefully.

3

Write the function to clone the linked list with random pointers

Write a function called copyRandomList that takes the head node head: Node | null and returns a new head node of the cloned list. Use the approach of interleaving cloned nodes between original nodes, then assign random pointers, and finally separate the cloned list from the original.

DSA Typescript

function copyRandomList(head: Node | null): Node | null {
    if (!head) return null;
    // Step 1: Create new nodes and insert them after original nodes
    let current: Node | null = head;
    while (current) {
        const newNode = new Node(current.val);
        newNode.next = current.next;
        current.next = newNode;
        current = newNode.next;
    // Step 2: Assign random pointers for the new nodes
    current = head;
    while (current) {
        if (current.random) {
            current.next!.random = current.random.next;
        } else {
            current.next!.random = null;
        }
        current = current.next!.next;
    // Step 3: Separate the new list from the original list
    current = head;
    const newHead = head.next;
    while (current) {
        const copy = current.next!;
        current.next = copy.next;
        if (copy.next) {
            copy.next = copy.next.next;
        } else {
            copy.next = null;
        }
        current = current.next;
    return newHead;
// Print cloned list

Hint

First, put a copy of each node right after it. Then fix the random arrows for the copies. Finally, pull out the copies to form the new list.

4

Print the cloned list showing values and random pointers

Call copyRandomList with node1 as input and store the result in clonedHead. Then use a while loop with a variable current to traverse clonedHead. For each node, print a line with the format: Node val: X, Random points to: Y where X is the node's val and Y is the val of the random node or null if no random pointer.

DSA Typescript

Hint

Walk through the cloned list and print each node's value and the value of its random pointer or null if none.

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