Clone Linked List with Random Pointer in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Cloning a Linked List with Random Pointers

What is the printed output of the following C++ code that clones a linked list with random pointers? The print format is: (random_val) -> ... -> null

DSA C++

struct Node {
    int val;
    Node* next;
    Node* random;
    Node(int _val) : val(_val), next(nullptr), random(nullptr) {}
};

#include <iostream>
#include <unordered_map>

Node* cloneList(Node* head) {
    if (!head) return nullptr;
    std::unordered_map<Node*, Node*> map;
    Node* curr = head;
    while (curr) {
        map[curr] = new Node(curr->val);
        curr = curr->next;
    }
    curr = head;
    while (curr) {
        map[curr]->next = map[curr->next];
        map[curr]->random = map[curr->random];
        curr = curr->next;
    }
    return map[head];
}

void printList(Node* head) {
    while (head) {
        std::cout << head->val << "(";
        if (head->random) std::cout << head->random->val;
        else std::cout << "null";
        std::cout << ") -> ";
        head = head->next;
    }
    std::cout << "null" << std::endl;
}

int main() {
    Node* n1 = new Node(1);
    Node* n2 = new Node(2);
    Node* n3 = new Node(3);
    n1->next = n2; n2->next = n3;
    n1->random = n3; n2->random = n1; n3->random = nullptr;
    Node* cloned = cloneList(n1);
    printList(cloned);
    return 0;
}

A 1(2) -> 2(3) -> 3(null) -> null

B 1(3) -> 2(1) -> 3(null) -> null

C 1(1) -> 2(2) -> 3(3) -> null

D 1(null) -> 2(3) -> 3(1) -> null

💡 Hint

Trace the mapping of original nodes to cloned nodes and how random pointers are assigned.

The cloneList function creates new nodes for each original node and uses a map to assign next and random pointers correctly. The original list has random pointers: 1->3, 2->1, 3->null, so the cloned list prints the same pattern.

🧠 Conceptual

intermediate

Number of Nodes in Cloned List

If the original linked list has 5 nodes, how many nodes will the cloned linked list have after cloning with random pointers?

A 5

B 10

C 0

D Depends on random pointers

💡 Hint

Each original node corresponds to exactly one cloned node.

The cloning process creates exactly one new node for each original node, regardless of random pointers. So the cloned list has the same number of nodes as the original.

🔧 Debug

advanced

Identify the Error in Cloning Code

What error will the following code produce when cloning a linked list with random pointers?

DSA C++

Node* cloneList(Node* head) {
    if (!head) return nullptr;
    Node* curr = head;
    while (curr) {
        Node* 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;
    Node* copyHead = head->next;
    while (curr) {
        Node* copy = curr->next;
        curr->next = copy->next;
        if (copy->next) copy->next = copy->next->next;
        curr = curr->next;
    }
    return copyHead;
}

int main() {
    Node* n1 = new Node(1);
    n1->random = n1;
    Node* cloned = cloneList(n1);
    std::cout << cloned->random->val << std::endl;
    return 0;
}

A Runtime error due to null pointer dereference

B Outputs 0 instead of 1

C Compilation error due to missing headers

D Outputs 1 correctly

💡 Hint

Check how random pointers are assigned in the interleaved list.

This is the classic O(1) space cloning method. It correctly assigns random pointers and restores the original list. The output prints 1 as expected.

❓ Predict Output

advanced

Output of Cloning with Null Random Pointers

What is the output of this code that clones a linked list where all random pointers are null? The print format is: (random_val) -> ... -> null

DSA C++

struct Node {
    int val;
    Node* next;
    Node* random;
    Node(int _val) : val(_val), next(nullptr), random(nullptr) {}
};

#include <iostream>
#include <unordered_map>

Node* cloneList(Node* head) {
    if (!head) return nullptr;
    std::unordered_map<Node*, Node*> map;
    Node* curr = head;
    while (curr) {
        map[curr] = new Node(curr->val);
        curr = curr->next;
    }
    curr = head;
    while (curr) {
        map[curr]->next = map[curr->next];
        map[curr]->random = map[curr->random];
        curr = curr->next;
    }
    return map[head];
}

void printList(Node* head) {
    while (head) {
        std::cout << head->val << "(";
        if (head->random) std::cout << head->random->val;
        else std::cout << "null";
        std::cout << ") -> ";
        head = head->next;
    }
    std::cout << "null" << std::endl;
}

int main() {
    Node* n1 = new Node(10);
    Node* n2 = new Node(20);
    Node* n3 = new Node(30);
    n1->next = n2; n2->next = n3;
    n1->random = nullptr; n2->random = nullptr; n3->random = nullptr;
    Node* cloned = cloneList(n1);
    printList(cloned);
    return 0;
}

A 10(null) -> 20(null) -> 30(null) -> null

B 10(10) -> 20(20) -> 30(30) -> null

C 10(20) -> 20(30) -> 30(null) -> null

D null

💡 Hint

Random pointers are all null, so cloned nodes have random as null.

Since all random pointers are null in the original list, the cloned list will also have random pointers as null for all nodes.

🧠 Conceptual

expert

Space Complexity of Cloning Methods

Which cloning method uses O(1) extra space when cloning a linked list with random pointers?

A Recursively cloning nodes and random pointers

B Using a hash map to store original to cloned node mappings

C Interleaving cloned nodes between original nodes and then separating

D Creating a new list and assigning random pointers by searching original list

💡 Hint

Think about which method avoids extra data structures.

The interleaving method inserts cloned nodes between original nodes, uses existing pointers to assign random pointers, and then separates the lists, achieving O(1) extra space.

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