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

Clone Linked List with Random Pointer

📖 Scenario: Imagine 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 structure is used in complex applications like undo operations or social network friend suggestions.

🎯 Goal: You will build a program to create a deep copy (clone) of this linked list with random pointers. The clone should have new nodes with the same values and the same next and random pointer structure as the original.

📋 What You'll Learn

Create a linked list node structure with val, next, and random pointers

Build an initial linked list with 3 nodes and specific next and random pointers

Add a helper variable to assist cloning

Implement the cloning logic to create a deep copy of the list

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

💡 Why This Matters

🌍 Real World

Cloning linked lists with random pointers is useful in applications like undo-redo systems, complex data caching, and social network friend suggestions where relationships are not linear.

💼 Career

Understanding how to clone complex data structures is important for software engineers working with advanced data manipulation, memory management, and designing efficient algorithms.

1

Create the linked list node structure and initial list

Define a struct called Node with an integer val, and two pointers next and random of type Node*. Then create three nodes named node1, node2, and node3 with values 1, 2, and 3 respectively. Link them so that node1.next = &node2, node2.next = &node3, and node3.next = nullptr. Set the random pointers as node1.random = &node3, node2.random = &node1, and node3.random = &node2. Finally, create a pointer head pointing to &node1.

DSA C++

// Define struct Node and create nodes node1, node2, node3 with next and random pointers
// Your code here

Hint

Start by defining the Node struct with the required members. Then create three nodes with values 1, 2, and 3. Link their next and random pointers exactly as described.

2

Add a helper pointer for cloning

Create a pointer variable called current and set it to head. This will help us traverse the list during cloning.

DSA C++

struct Node {
    int val;
    Node* next;
    Node* random;
};

Node node1{1, nullptr, nullptr};
Node node2{2, nullptr, nullptr};
Node node3{3, nullptr, nullptr};

node1.next = &node2;
node2.next = &node3;
node3.next = nullptr;

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

Node* head = &node1;

// Create a pointer current and set it to head
// Your code here

Hint

Just create a pointer current and assign it the value of head.

3

Clone the linked list with random pointers

Write code to clone the linked list with random pointers. Use the following approach: For each node in the original list, create a new node with the same val and insert it right after the original node. Then set the random pointer of the new node to the next of the original node's random. Finally, separate the new nodes to form the cloned list. Use variables current and cloneHead as needed.

DSA C++

struct Node {
    int val;
    Node* next;
    Node* random;
};

Node node1{1, nullptr, nullptr};
Node node2{2, nullptr, nullptr};
Node node3{3, nullptr, nullptr};

node1.next = &node2;
node2.next = &node3;
node3.next = nullptr;

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

Node* head = &node1;

Node* current = head;

// Clone the list with random pointers
// Your code here

Hint

First, create new nodes and insert them after each original node. Then assign the random pointers of the new nodes. Finally, detach the new nodes to form the cloned list.

4

Print the cloned list showing values and random pointers

Write a loop to print each node's val and the val of its random pointer in the cloned list starting from cloneHead. For each node, print in the format: Node val: X, Random val: Y. If the random pointer is null, print Random val: nullptr.

DSA C++

struct Node {
    int val;
    Node* next;
    Node* random;
};

Node node1{1, nullptr, nullptr};
Node node2{2, nullptr, nullptr};
Node node3{3, nullptr, nullptr};

node1.next = &node2;
node2.next = &node3;
node3.next = nullptr;

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

Node* head = &node1;

Node* current = head;

// Step 1: Insert cloned nodes after original nodes
while (current != nullptr) {
    Node* newNode = new Node{current->val, current->next, nullptr};
    current->next = newNode;
    current = newNode->next;
}

// Step 2: Set random pointers for cloned nodes
current = head;
while (current != nullptr) {
    if (current->random != nullptr) {
        current->next->random = current->random->next;
    }
    current = current->next->next;
}

// Step 3: Separate the cloned list from the original list
current = head;
Node* cloneHead = nullptr;
Node* cloneCurrent = nullptr;
if (current != nullptr) {
    cloneHead = current->next;
    cloneCurrent = cloneHead;
    current->next = cloneCurrent->next;
    current = current->next;
}

while (current != nullptr) {
    cloneCurrent->next = current->next;
    cloneCurrent = cloneCurrent->next;
    current->next = cloneCurrent->next;
    current = current->next;
}

// Print the cloned list nodes with val and random val
// Your code here

Hint

Traverse the cloned list starting from cloneHead. For each node, print its value and the value of its random pointer if it exists, otherwise print nullptr.

Practice

1. What is the main challenge when cloning a linked list with a random pointer?

easy

A. Maintaining the correct random pointer connections in the cloned list

B. Copying the data values of each node

C. Reversing the linked list before cloning

D. Sorting the linked list nodes after cloning

Solution

1. Step 1: Understand the structure of the linked list

   The linked list has two pointers: next and random. The next pointer points to the next node, and the random pointer can point to any node or null.

2. Step 2: Identify the cloning challenge

   While copying nodes is straightforward, correctly assigning the random pointers in the cloned list is tricky because they can point anywhere in the original list.

3. Final Answer:

   Maintaining the correct random pointer connections in the cloned list -> Option A

4. Quick Check:

   Random pointer cloning = main challenge [OK]

Hint: Focus on copying random pointers correctly [OK]

Common Mistakes:

• Ignoring random pointers during cloning
• Only copying next pointers
• Assuming random pointers follow next pointers

2. Which of the following is the correct way to declare a node structure for a linked list with a random pointer in C++?

easy

A. struct Node { int data; Node* next; Node* random; };

B. struct Node { int data; Node next; Node random; };

C. struct Node { int data; Node* next; int random; };

D. struct Node { int data; Node next; int random; };

Solution

1. Step 1: Understand pointer usage in C++ structs

   To link nodes, pointers to Node type are needed for next and random pointers.

2. Step 2: Check each option's correctness

   struct Node { int data; Node* next; Node* random; }; uses Node* for next and random, which is correct. Those using Node without pointer are invalid. struct Node { int data; Node* next; int random; }; uses int for random, which is incorrect.

3. Final Answer:

   struct Node { int data; Node* next; Node* random; }; -> Option A

4. Quick Check:

   Use pointers for next and random [OK]

Hint: Use Node* for next and random pointers [OK]

Common Mistakes:

• Using Node instead of Node* for pointers
• Using int type for random pointer
• Missing semicolon after struct

3. Given the following code snippet for cloning a linked list with random pointers, what will be the output of the cloned list's data sequence?

struct Node {
  int data;
  Node* next;
  Node* random;
  Node(int x) : data(x), next(nullptr), random(nullptr) {}
};

// Original list: 1 -> 2 -> 3 -> null
// random pointers: 1.random = 3, 2.random = 1, 3.random = 2

// After cloning, print cloned list data:
Node* cloneHead = cloneLinkedList(head); // Assume correct cloning function
Node* temp = cloneHead;
while(temp) {
  std::cout << temp->data << " ";
  temp = temp->next;
}

medium

A. 1 3 2

B. 3 2 1

C. 1 2 3

D. 2 1 3

Solution

1. Step 1: Understand the cloning process

   The cloneLinkedList function creates a new list with the same data and next pointer order as the original list.

2. Step 2: Trace the output loop

   The loop prints data of cloned nodes in order: first node data 1, then 2, then 3.

3. Final Answer:

   1 2 3 -> Option C

4. Quick Check:

   Cloned list data order = original order [OK]

Hint: Cloned list preserves original node order [OK]

Common Mistakes:

• Confusing random pointer order with next pointer order
• Printing random pointer data instead of next
• Assuming reversed list after cloning

4. Identify the error in the following code snippet for cloning a linked list with random pointers:

Node* cloneLinkedList(Node* head) {
  if (!head) return nullptr;
  Node* curr = head;
  while (curr) {
    Node* newNode = new Node(curr->data);
    newNode->next = curr->next;
    curr->next = newNode;
    curr = newNode->next;
  }
  curr = head;
  while (curr) {
    if (curr->random) {
      curr->next->random = curr->random->next;
    }
    curr = curr->next->next;
  }
  Node* original = head, *copy = head->next, *temp = copy;
  while (original && copy) {
    original->next = original->next->next;
    copy->next = copy->next ? copy->next->next : nullptr;
    original = original->next;
    copy = copy->next;
  }
  return temp;
}

medium

A. The random pointer assignment is incorrect

B. No error; the code correctly clones the list

C. The final while loop incorrectly restores original and cloned lists

D. The first while loop incorrectly inserts cloned nodes

Solution

1. Step 1: Analyze node insertion loop

   The first loop inserts cloned nodes after each original node correctly.

2. Step 2: Analyze random pointer assignment and list separation

   The second loop assigns random pointers correctly. The final loop restores original and cloned lists properly.

3. Final Answer:

   No error; the code correctly clones the list -> Option B

4. Quick Check:

   Code follows standard cloning steps [OK]

Hint: Check each step matches cloning algorithm phases [OK]

Common Mistakes:

• Misreading pointer assignments
• Assuming random pointer assignment is wrong without checking
• Confusing original and cloned list restoration

5. You want to clone a linked list with random pointers but without using extra space for a hash map. Which approach below correctly achieves this with O(1) extra space?

hard

A. Reverse the original list, clone it, then reverse both lists back

B. Use a hash map to store original to cloned node mappings

C. Traverse the list twice, first to copy data, second to copy random pointers using a vector

D. Create cloned nodes interleaved with original nodes, assign random pointers, then separate lists

Solution

1. Step 1: Understand space constraints

   Using extra data structures like hash maps or vectors uses extra space.

2. Step 2: Identify O(1) space cloning method

   Interleaving cloned nodes with original nodes allows assigning random pointers without extra space, then separating lists restores original and cloned lists.

3. Final Answer:

   Create cloned nodes interleaved with original nodes, assign random pointers, then separate lists -> Option D

4. Quick Check:

   Interleaving nodes = O(1) space cloning [OK]

Hint: Interleave cloned nodes to avoid extra space [OK]

Common Mistakes:

• Using hash maps when O(1) space is required
• Trying to clone by reversing list
• Using extra arrays or vectors unnecessarily