Clone Linked List with Random Pointer in DSA Javascript

Mental Model

We want to make a new linked list that looks exactly like the original, including special random links, without mixing the two lists.

Analogy: Imagine copying a group of friends where each friend points to another friend randomly. You want to create a new group with the same friendships but keep the groups separate.

Original List:
1 -> 2 -> 3 -> null
|     |     |
↓     ↓     ↓
3     1     2
(random pointers)

Goal:
Clone List:
1' -> 2' -> 3' -> null
|      |      |
↓      ↓      ↓
3'     1'     2'
(random pointers)

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, without changing the original list.

Step 1: Insert cloned nodes after each original node

1 -> 1' -> 2 -> 2' -> 3 -> 3' -> null
(random pointers unchanged)

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

Step 2: Assign 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'
List: 1 -> 1' -> 2 -> 2' -> 3 -> 3' -> null

Why: We use original node's random to find the clone's random by next pointer.

Step 3: Separate the cloned list from the original list

Original: 1 -> 2 -> 3 -> null
Clone: 1' -> 2' -> 3' -> null
Both have correct next and random pointers

Why: We restore original list and extract the cloned list as separate lists.

Result:

Cloned List:
1' -> 2' -> 3' -> null
1'.random -> 3'
2'.random -> 1'
3'.random -> 2'

Annotated Code

DSA Javascript

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

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

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

  // Step 2: Assign 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 list
  curr = head;
  const clonedHead = head.next;
  while (curr) {
    const cloned = curr.next;
    curr.next = cloned.next;
    cloned.next = cloned.next ? cloned.next.next : null;
    curr = curr.next;
  }

  return clonedHead;
}

// 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) {
  let curr = head;
  let result = '';
  while (curr) {
    const randomVal = curr.random ? curr.random.val : 'null';
    result += `${curr.val}(random:${randomVal}) -> `;
    curr = curr.next;
  }
  result += 'null';
  console.log(result);
}

printList(node1); // Original list
printList(cloned); // Cloned list

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

Insert cloned nodes right after original nodes to link clones with originals

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

Set cloned node's random pointer using original node's random pointer's next

while (curr) { const cloned = curr.next; curr.next = cloned.next; cloned.next = cloned.next ? cloned.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

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 (three passes)

Space: O(1) because we clone nodes in place without extra data structures

vs Alternative: Naive approach uses a hash map to store original-to-clone mapping with O(n) extra space; this approach saves space by weaving clones into original list

Edge Cases

empty list (head is null)

Returns null immediately without errors

DSA Javascript

if (!head) return null;

list with one node where random pointer is null

Cloned list has one node with random pointer null

DSA Javascript

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

list with random pointers pointing to self

Cloned nodes' random pointers correctly point to themselves

DSA Javascript

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

When to Use This Pattern

When you see a linked list with an extra random pointer and need to clone it exactly, use the weaving technique to link clones next to originals for easy random pointer assignment.

Common Mistakes

Mistake: Not restoring the original list after cloning, leaving the original and cloned nodes mixed
Fix: Separate the lists by fixing next pointers in the final step to restore original and extract clone

Mistake: Assigning random pointers incorrectly by not using the next pointer of the original's random node
Fix: Set cloned random as curr.next.random = curr.random.next to point to cloned random node

Summary

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

Use it when you need an exact independent copy of a complex linked list with random links.

The key is to weave cloned nodes into the original list 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 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