Clone Linked List with Random Pointer in DSA C++

Mental Model

We want to make a new linked list that looks exactly like the original, including special random links that can point anywhere in the list.

Analogy: Imagine copying a group photo where each person is holding a string tied to another person randomly. You must copy both the people and the strings exactly so the new group looks the same.

Original list:
1 -> 2 -> 3 -> null
Random pointers:
1.random -> 3
2.random -> 1
3.random -> 2

Dry Run Walkthrough

Input: list: 1 -> 2 -> 3, 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

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 of clones easily by using original nodes

Step 2: Assign random pointers for cloned nodes using original nodes

1.random -> 3, 1'.random -> 3'
2.random -> 1, 2'.random -> 1'
3.random -> 2, 3'.random -> 2'

Why: We use original node's random to set clone's random to the clone of that node

Step 3: Separate the cloned list from the original list

Original: 1 -> 2 -> 3 -> null
Clone: 1' -> 2' -> 3' -> null
Random pointers preserved in clone

Why: We restore original list and extract the cloned list as a separate copy

Result:

Cloned list:
1' -> 2' -> 3' -> null
Random pointers:
1'.random -> 3'
2'.random -> 1'
3'.random -> 2'

Annotated Code

DSA C++

#include <iostream>
using namespace std;

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

Node* cloneLinkedList(Node* head) {
    if (!head) return nullptr;

    // Step 1: Insert cloned nodes after original nodes
    Node* curr = head;
    while (curr) {
        Node* clone = new Node(curr->val);
        clone->next = curr->next;
        curr->next = clone;
        curr = clone->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;
    Node* cloneHead = head->next;
    Node* cloneCurr = cloneHead;
    while (curr) {
        curr->next = curr->next->next;
        if (cloneCurr->next) {
            cloneCurr->next = cloneCurr->next->next;
        } else {
            cloneCurr->next = nullptr;
        }
        curr = curr->next;
        cloneCurr = cloneCurr->next;
    }

    return cloneHead;
}

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

int main() {
    // Create original list 1->2->3
    Node* n1 = new Node(1);
    Node* n2 = new Node(2);
    Node* n3 = new Node(3);
    n1->next = n2;
    n2->next = n3;

    // Setup random pointers
    n1->random = n3; // 1.random -> 3
    n2->random = n1; // 2.random -> 1
    n3->random = n2; // 3.random -> 2

    cout << "Original list:" << endl;
    printList(n1);

    Node* cloned = cloneLinkedList(n1);

    cout << "Cloned list:" << endl;
    printList(cloned);

    return 0;
}

while (curr) { Node* clone = new Node(curr->val); clone->next = curr->next; curr->next = clone; curr = clone->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 random pointers of clones using original nodes' random pointers

while (curr) { curr->next = curr->next->next; if (cloneCurr->next) { cloneCurr->next = cloneCurr->next->next; } else { cloneCurr->next = nullptr; } curr = curr->next; cloneCurr = cloneCurr->next; }

Separate the cloned list from the original list restoring original next pointers

Output

Original list:

1 (Random: 3) -> 2 (Random: 1) -> 3 (Random: 2) -> null

Cloned list:

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 proportional to n nodes

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

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

Edge Cases

Empty list (head is nullptr)

Function returns nullptr immediately without errors

DSA C++

if (!head) return nullptr;

List with one node and random pointer to itself

Cloned list has one node with random pointer correctly pointing to itself

DSA C++

while (curr) { if (curr->random) { curr->next->random = curr->random->next; } curr = curr->next->next; }

Random pointers are null for all nodes

Cloned nodes have random pointers set to nullptr correctly

DSA C++

if (curr->random) { 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 copy it exactly, use the weaving technique to clone nodes in place for O(1) space cloning.

Common Mistakes

Mistake: Not inserting cloned nodes between original nodes, making it hard to assign random pointers correctly
Fix: Insert cloned nodes immediately after original nodes to link clones with originals for easy random pointer assignment

Mistake: Forgetting to restore the original list's next pointers after cloning
Fix: Separate the cloned list and restore original next pointers in the final step

Mistake: Assigning random pointers of clones incorrectly by not using original node's random next
Fix: Set clone's random to original's random's next node

Summary

Clones a linked list with next and random pointers preserving all connections.

Use when you need an exact deep copy of a complex linked list with random pointers.

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. 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