Clone Linked List with Random Pointer in DSA C++ - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to create a new node with the same value as the current node.

DSA C++

Node* clone = new Node([1]);

Drag options to blanks, or click blank then click option'

Acurr->random

Bcurr->next

Ccurr->val

Dcurr

Attempts:

3 left

💡 Hint

Common Mistakes

Using curr->next or curr->random instead of curr->val.

Trying to copy the whole node instead of just the value.

We need to copy the value of the current node to create the clone node.

2fill in blank

medium

Complete the code to insert the cloned node right after the current node.

DSA C++

clone->next = [1];
curr->next = clone;

Drag options to blanks, or click blank then click option'

Anullptr

Bcurr->random

Cclone

Dcurr->next

Attempts:

3 left

💡 Hint

Common Mistakes

Setting clone->next to curr->random or nullptr.

Not updating curr->next to point to the clone.

We set clone->next to curr->next to insert the clone node after curr.

3fill in blank

hard

Fix the error in setting the random pointer of the cloned node.

DSA C++

if (curr->random != nullptr) {
    curr->next->random = [1];
}

Drag options to blanks, or click blank then click option'

Anullptr

Bcurr->random->next

Ccurr->random

Dcurr->next->random

Attempts:

3 left

💡 Hint

Common Mistakes

Assigning curr->random directly instead of its clone.

Assigning nullptr or curr->next->random incorrectly.

The cloned node's random pointer should point to the clone of curr->random, which is curr->random->next.

4fill in blank

hard

Fill both blanks to restore the original list and extract the cloned list.

DSA C++

Node* original = head;
Node* copy = head->next;
Node* copyHead = copy;
while (original != nullptr) {
    original->next = [1];
    copy->next = [2];
    original = original->next;
    copy = copy->next;
}

Drag options to blanks, or click blank then click option'

Aoriginal->next->next

Bcopy->next->next

Ccopy->next

Doriginal->next

Attempts:

3 left

💡 Hint

Common Mistakes

Not skipping nodes correctly, causing cycles or broken lists.

Assigning copy->next incorrectly.

To restore the original list, original->next should skip the clone node and point to original->next->next. For the cloned list, copy->next should point to copy->next.

5fill in blank

hard

Fill all three blanks to complete the clone function returning the cloned list head.

DSA C++

Node* copyRandomList(Node* head) {
    if (head == nullptr) return nullptr;

    Node* curr = head;
    while (curr != nullptr) {
        Node* clone = new Node([1]);
        clone->next = curr->next;
        curr->next = clone;
        curr = clone->next;
    }

    curr = head;
    while (curr != nullptr) {
        if (curr->random != nullptr) {
            curr->next->random = [2];
        }
        curr = curr->next->next;
    }

    curr = head;
    Node* copy = head->next;
    Node* copyHead = copy;
    while (curr != nullptr) {
        curr->next = [3];
        copy->next = copy->next != nullptr ? copy->next->next : nullptr;
        curr = curr->next;
        copy = copy->next;
    }

    return copyHead;
}

Drag options to blanks, or click blank then click option'

Acurr->val

Bcurr->random->next

Ccurr->next->next

Dcurr->random

Attempts:

3 left

💡 Hint

Common Mistakes

Copying wrong values to clone nodes.

Setting random pointers incorrectly.

Not restoring the original list properly.

The clone node copies curr->val. The clone's random pointer is curr->random->next. To restore the original list, curr->next should point to curr->next->next.

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