Clone Linked List with Random Pointer in DSA Typescript

Mental Model

We want to make a new linked list that looks exactly like the original, including special random links that can point anywhere in the list.

Analogy: Imagine copying a group of friends standing in a line, where each friend also points randomly to another friend. We want to create a new group that stands in the same order and keeps the same random friendships.

Original list:
1 -> 2 -> 3 -> null
|     |     |
v     v     v
3     1     2

Clone list after copying values:
1 -> 2 -> 3 -> null

Random pointers need to be set to match original.

Dry Run Walkthrough

Input: list: 1 -> 2 -> 3 -> null with random pointers: 1.random -> 3, 2.random -> 1, 3.random -> 2

Goal: Create a new list that copies both next and random pointers exactly

Step 1: Insert cloned nodes after each original node

1 -> 1' -> 2 -> 2' -> 3 -> 3' -> null

Why: This helps us link random pointers easily by using the next pointers

Step 2: Set random pointers for cloned nodes using original nodes' random pointers

1.random -> 3, 1'.random -> 3'
2.random -> 1, 2'.random -> 1'
3.random -> 2, 3'.random -> 2'

Why: We use the interleaved structure to find the clone of the random target quickly

Step 3: Separate the cloned list from the original list

Original: 1 -> 2 -> 3 -> null
Clone: 1' -> 2' -> 3' -> null

Why: We restore the original list and get the cloned list as a separate copy

Result:

Cloned list: 1' -> 2' -> 3' -> null with random pointers: 1'.random -> 3', 2'.random -> 1', 3'.random -> 2'

Annotated 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 cloneLinkedListWithRandomPointer(head: Node | null): Node | null {
  if (!head) return null;

  // Step 1: Insert cloned nodes after original nodes
  let curr: Node | null = head;
  while (curr) {
    const clone = new Node(curr.val, curr.next, null);
    curr.next = clone;
    curr = clone.next;
  }

  // Step 2: Set random pointers for cloned nodes
  curr = head;
  while (curr) {
    if (curr.random) {
      curr.next!.random = curr.random.next;
    }
    curr = curr.next!.next;
  }

  // Step 3: Separate cloned list from original
  curr = head;
  const cloneHead = head.next;
  while (curr) {
    const clone = curr.next!;
    curr.next = clone.next;
    clone.next = clone.next ? clone.next.next : null;
    curr = curr.next;
  }

  return cloneHead;
}

// Driver code to test
const node3 = new Node(3);
const node2 = new Node(2);
const node1 = new Node(1);
node1.next = node2;
node2.next = node3;
node1.random = node3;
node2.random = node1;
node3.random = node2;

const cloned = cloneLinkedListWithRandomPointer(node1);

// Function to print list with random pointers
function printList(head: Node | null): void {
  let curr = head;
  const result: string[] = [];
  while (curr) {
    const randomVal = curr.random ? curr.random.val : 'null';
    result.push(`${curr.val}(random:${randomVal})`);
    curr = curr.next;
  }
  console.log(result.join(' -> ') + ' -> null');
}

printList(cloned);

while (curr) { const clone = new Node(curr.val, curr.next, null); curr.next = clone; curr = clone.next; }

Insert cloned node right after each original node to interleave lists

while (curr) { if (curr.random) { curr.next!.random = curr.random.next; } curr = curr.next!.next; }

Assign random pointer of cloned node using original node's random pointer

while (curr) { const clone = curr.next!; curr.next = clone.next; clone.next = clone.next ? clone.next.next : null; curr = curr.next; }

Restore original list and extract cloned list by fixing next pointers

Output

1(random:3) -> 2(random:1) -> 3(random:2) -> null

Complexity Analysis

Time: O(n) because we traverse the list a constant number of times proportional to n nodes

Space: O(1) extra space because we do not use additional data structures, only pointers

vs Alternative: Naive approach uses a hash map to store original-to-clone mapping with O(n) extra space, this method saves space by interleaving nodes

Edge Cases

empty list (head is null)

function returns null immediately without processing

DSA Typescript

if (!head) return null;

list with one node where random pointer is null

clone node is created with random pointer null correctly

DSA Typescript

if (curr.random) { curr.next!.random = curr.random.next; }

list with random pointers pointing to self

random pointers in clone correctly point to cloned self node

DSA Typescript

curr.next!.random = curr.random.next;

When to Use This Pattern

When you see a linked list with random pointers and need to copy it exactly, use the interleaving clone pattern to handle random links efficiently.

Common Mistakes

Mistake: Not inserting cloned nodes between original nodes, making it hard to assign random pointers
Fix: Interleave cloned nodes immediately after original nodes to use next pointers for random assignment

Mistake: Forgetting to restore the original list after cloning
Fix: Separate the two lists by fixing next pointers in the final step

Mistake: Assigning random pointers incorrectly by not using the next of random node
Fix: Set clone.random = original.random.next to point to cloned target

Summary

Creates a deep copy of a linked list with next and random pointers.

Use when you need an exact duplicate of a complex linked list with arbitrary random links.

Interleave cloned nodes with original nodes to assign random pointers without extra space.

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