Clone a Linked List with Random Pointers in C++

This C++ program demonstrates how to clone a linked list where each node contains two pointers: one pointing to the next node in the usual linear sequence, and another random pointer that can point to any node in the list or to null.

Program Code

#include <iostream>

// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;

    Node(int _val) {
        val = _val;
        next = nullptr;
        random = nullptr;
    }
};

// Function to clone the linked list
Node* cloneList(Node* head) {
    if (!head) return nullptr;

    // Step 1: Create new nodes and interweave them with the original nodes
    for (Node* node = head; node != nullptr; node = node->next->next) {
        Node* newNode = new Node(node->val);
        newNode->next = node->next;
        node->next = newNode;
    }

    // Step 2: Assign random pointers for the cloned nodes
    for (Node* node = head; node != nullptr; node = node->next->next) {
        if (node->random) {
            node->next->random = node->random->next;
        }
    }

    // Step 3: Separate the cloned list from the original list
    Node* pseudoHead = new Node(0);
    Node* copy = pseudoHead;
    for (Node* node = head; node != nullptr; node = node->next) {
        copy->next = node->next;
        copy = copy->next;
        node->next = node->next->next;
    }

    return pseudoHead->next;
}

// Helper function to print the linked list
void printList(Node* node) {
    while (node != nullptr) {
        std::cout << "Node val: " << node->val << ", Random val: ";
        if (node->random) std::cout << node->random->val;
        else std::cout << "null";
        std::cout << std::endl;
        node = node->next;
    }
}

int main() {
    // Create the linked list: 1->2->3 with random pointers
    Node* node1 = new Node(1);
    Node* node2 = new Node(2);
    Node* node3 = new Node(3);
    node1->next = node2;
    node2->next = node3;
    node1->random = node3;
    node2->random = node1;
    node3->random = node2;

    std::cout << "Original List:" << std::endl;
    printList(node1);

    Node* clonedList = cloneList(node1);
    std::cout << "Cloned List:" << std::endl;
    printList(clonedList);

    return 0;
}

Explanation of the Code

The program starts with a class definition for the list node, which includes fields for value, next pointer, and random pointer. The cloneList function consists of three main steps:

• Interweaving cloned nodes with original nodes: It inserts a new node just after every original node, effectively creating a cloned node right next to its original.
• Setting random pointers: For each original node’s random pointer, the corresponding cloned node’s random pointer is set to the next of the original node’s random pointer.
• Separating the cloned nodes from the original list: It restores the original list and extracts the cloned nodes to form a separate cloned list.

Conclusion

This C++ program efficiently clones a linked list with random pointers by interweaving cloned nodes with their originals, setting up proper random pointers, and then separating the cloned list. This technique ensures that the original list remains unmodified while creating a deep copy of the list, including the complex random pointer connections.