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

Clone Linked List with Random Pointer

📖 Scenario: You are working on a social media app where each user has a friend list. Each friend is represented as a node in a linked list. Besides the usual next friend, each friend node also has a random pointer to any other friend in the list (or null) representing a special connection.To create a backup of this friend list, you need to clone the entire linked list including the random connections.

🎯 Goal: Build a JavaScript program to clone a linked list where each node has a next pointer and a random pointer. The clone should be a deep copy with all next and random pointers correctly assigned.

📋 What You'll Learn

Create a linked list with nodes having val, next, and random properties

Set up a configuration variable to help map original nodes to their clones

Implement the cloning logic to create new nodes and assign next and random pointers

Print the cloned linked list in a readable format showing val and the random node's val or null

💡 Why This Matters

🌍 Real World

Cloning complex linked data structures is useful in social networks, game state saving, and undo-redo systems where objects have multiple references.

💼 Career

Understanding deep copy of linked structures with random pointers is a common interview question and helps in mastering pointer manipulation and hash map usage.

1

Create the original linked list with random pointers

Create a class called Node with properties val, next, and random. Then create three nodes with values 1, 2, and 3. Link them with next pointers: node1.next = node2, node2.next = node3, node3.next = null. Set random pointers as: node1.random = node3, node2.random = node1, node3.random = node2.

DSA Javascript

# Your code here to create Node class and three linked nodes with next and random pointers

Hint

Define a Node class first. Then create three nodes and link their next and random pointers exactly as described.

2

Create a map to hold original to cloned node references

Create a new empty Map called nodeMap to store the mapping from original nodes to their cloned nodes.

DSA Javascript

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

const node1 = new Node(1);
const node2 = new Node(2);
const node3 = new Node(3);

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

node1.random = node3;
node2.random = node1;
node3.random = node2;

// Create a Map to hold original to cloned node references
// Your code here

Hint

Use const nodeMap = new Map() to create the map.

3

Clone the linked list nodes and assign next and random pointers

Write code to clone the linked list starting from node1. First, iterate through the original list and create new nodes with the same val, storing them in nodeMap with original nodes as keys. Then iterate again to assign next and random pointers for the cloned nodes using nodeMap.

DSA Javascript

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

const node1 = new Node(1);
const node2 = new Node(2);
const node3 = new Node(3);

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

node1.random = node3;
node2.random = node1;
node3.random = node2;

const nodeMap = new Map();

// Clone nodes and store in nodeMap
// Assign next and random pointers for cloned nodes
// Your code here

Hint

Use two loops: one to create cloned nodes and store them in nodeMap, another to assign next and random pointers using the map.

4

Print the cloned linked list with random pointers

Write a function called printList that takes a node and prints each node's val and the val of its random pointer (or null) in the format: val (random: random_val) -> .... Then call printList with the cloned head node from nodeMap.get(node1).

DSA Javascript

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

const node1 = new Node(1);
const node2 = new Node(2);
const node3 = new Node(3);

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

node1.random = node3;
node2.random = node1;
node3.random = node2;

const nodeMap = new Map();

// First pass: clone nodes and store in map
let current = node1;
while (current !== null) {
    nodeMap.set(current, new Node(current.val));
    current = current.next;
}

// Second pass: assign next and random pointers
current = node1;
while (current !== null) {
    nodeMap.get(current).next = current.next ? nodeMap.get(current.next) : null;
    nodeMap.get(current).random = current.random ? nodeMap.get(current.random) : null;
    current = current.next;
}

// Write printList function and call it with cloned head
// Your code here

Hint

Loop through the cloned list and build a string showing each node's value and its random pointer's value or null. Then print the string.

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