Clone Linked List with Random Pointers 🎯

Welcome back to CodeYourCraft! Today, we're diving into an exciting topic: Cloning Linked Lists with Random Pointers. This lesson is perfect for beginners and intermediates, so let's get started!

What are Linked Lists and Random Pointers? 📝

Before we dive into cloning, let's review what a Linked List is and introduce Random Pointers.

A Linked List is a linear data structure where each element, called a node, consists of data and a reference (or link) to the next node in the sequence.

In some cases, a Linked List may also have a random pointer, which points to any node in the list or even to nodes in another list. This makes Linked Lists with Random Pointers more complex and interesting!

Creating a Linked List with Random Pointers 💡

Let's create a simple Linked List with Random Pointers for a better understanding.

cpp

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

// Code to initialize the linked list

💡 Pro Tip: In this example, we use a Node struct to represent each node in the list. The data field stores the value, next points to the next node in the sequence, and random points to any node in the list or another list.

Cloning the Linked List 🎯

Now that we have a Linked List with Random Pointers, let's create a clone of it where each node in the cloned list points to the corresponding node in the original list.

cpp

Node* cloneList(Node* head) {
    // Create a dictionary to store nodes
    unordered_map<Node*, Node*> nodeMap;

    // Traverse the original list and create copies for each node
    for (Node* node = head; node != NULL; node = node->next) {
        Node* newNode = new Node();
        newNode->data = node->data;
        nodeMap[node] = newNode;
    }

    // Re-initialize random pointers for the cloned list
    for (Node* node = head; node != NULL; node = node->next) {
        if (node->random != NULL) {
            nodeMap[node]->random = nodeMap[node->random];
        }
    }

    // Connect the nodes in the cloned list
    for (Node* node = head; node != NULL; node = node->next) {
        Node* newNode = nodeMap[node];
        newNode->next = (node->next != NULL) ? nodeMap[node->next] : NULL;
    }

    return nodeMap[head];
}

💡 Pro Tip: In this example, we use an unordered_map to store references to each node in the original list. This helps us quickly find and connect nodes in the cloned list.

Testing Our Clone Function ✅

Let's test our clone function with a simple Linked List and verify that the clone is correct.

cpp

int main() {
    // Initialize the original Linked List
    Node* head = new Node();
    head->data = 1;
    head->next = new Node();
    head->next->data = 2;
    head->next->next = new Node();
    head->next->next->data = 3;
    head->next->next->next = new Node();
    head->next->next->next->data = 4;
    head->next->next->next->next = new Node();
    head->next->next->next->next->data = 5;

    // Set random pointers
    head->next->random = head->next->next->next;
    head->next->next->random = head;
    head->next->next->next->random = head->next;
    head->next->next->next->next->random = head->next->next;

    // Clone the Linked List
    Node* clonedHead = cloneList(head);

    // Print both lists
    printList(head);
    cout << endl;
    printList(clonedHead);

    return 0;
}

Challenge: Clone a Linked List with Random Pointers 🎯

Now that you've seen how to clone a Linked List with Random Pointers, it's time for a challenge! Write your own function to clone a Linked List with Random Pointers using the knowledge you've gained today.

Don't forget to create a simple test case to verify your solution. Good luck!