Problem Statement

Given the head of a special linked list of n nodes where each nodes contains an additional pointer called random which can point to any node in the list or null.

Construct a deep copy of the linked list where,

• n new nodes are created with corresponding values as original linked list.
• The random pointers point to the corresponding new nodes as per their arrangement in the original list.
• Return the head of the newly constructed linked list.

Note: For custom input, a n x 2 matrix is taken with each row having 2 values:[ val, random_index] where,

• val: an integer representing ListNode.val
• random_index: index of the node (0 - n-1) that the random pointer points to, otherwise -1.

Examples

Example 1:

Input: [[1, -1], [2, 0], [3, 4], [4, 1], [5, 2]]
Output: 1 2 3 4 5, true

Explanation: All the nodes in the new list have same corresponding values as original nodes.
All the random pointers point to their corresponding nodes in the new list.
'true' represents that the nodes and references were created new

Example 2:

Input: [[5, -1], [3, -1], [2, 1], [1, 1]]
Output: 5 3 2 1, true

Explanation: All the nodes in the new list have same corresponding values as original nodes.
All the random pointers point to their corresponding nodes in the new list.
'true' represents that the nodes and references were created new.

Different Approaches

1️⃣ Brute Force Approach

Intuition:

Create a deep copy of the original linked list and use a map to establish a relationship between the original nodes and their copied nodes.

We traverse the list first to create a copied node for each original node then traverse and establish the correct connections between the copied nodes similar to the arrangement of the next and random pointers of the original pointers.

Approach:

1. Begin by setting up a pointer to traverse the original linked list. Use an empty map to associate each original node with its copied counterpart.
2. As you traverse the original linked list, create a new node for each original node, copying its data. Store each new node in the map, linking it to the corresponding original node.
3. Traverse the original list again to set up the connections for the copied nodes. Use the map to find the copied nodes and establish their next and random pointers, ensuring they mimic the original structure.
4. Finally, retrieve the head of the copied list from the map by looking up the copied node corresponding to the original list's head. This gives you a deep copy of the entire linked list with the same structure and connections as the original.

Dry Run:

Code:

#include <bits/stdc++.h>

using namespace std;


// Definition of singly linked list
struct ListNode {
    int val;
    ListNode *next;
    ListNode *random;
    ListNode() {
        val = 0;
        next = NULL;
        random = NULL;
    }
    ListNode(int data1) {
        val = data1;
        next = NULL;
        random = NULL;
    }
    ListNode(int data1, ListNode *next1, ListNode* r) {
        val = data1;
        next = next1;
        random = r;
    }
};

class Solution {
public:
    // Function to clone linked list with random pointers
    ListNode* copyRandomList(ListNode* head) {
        // If the head is null, return null
        if (!head) return NULL;

        /*Create an unordered_map to map 
        original nodes to their corresponding copied nodes*/
        unordered_map<ListNode*, ListNode*> mpp;
        ListNode* temp = head;

        // Create copies of each node
        while (temp != NULL) {
            // Create new node with same value as original
            ListNode* newNode = new ListNode(temp->val);
            // Map to original node 
            mpp[temp] = newNode;
            // Move to next node
            temp = temp->next;
        }

        // Reset temp 
        temp = head;

        /*Connect the next and 
        random pointers of the 
        copied nodes using the map*/
        while (temp != NULL) {
            // Get copied node from the map
            ListNode* copyNode = mpp[temp];
            /*Set next pointer of copied node 
            to the copied node of the next 
            original node*/
            copyNode->next = mpp[temp->next];
            /*Set the random pointer of the 
            copied node to the copied node of 
            the random original node*/
            copyNode->random = mpp[temp->random];
            temp = temp->next;
        }

        // Return the head
        return mpp[head];
    }
};

// Function to print the linked list
void printClonedLinkedList(ListNode *head) {
    while (head != nullptr) {
        // Print the data of the current node
        cout << "Data: " << head->val;
        // Print the data of the random pointer, if it exists
        if (head->random != nullptr) {
            cout << ", Random: " << head->random->val;
        } else {
            cout << ", Random: nullptr";
        }
        cout << endl;
        // Move to the next node
        head = head->next;
    }
}

int main() {
    // Example linked list: 7 -> 14 -> 21 -> 28
    ListNode* head = new ListNode(7);
    head->next = new ListNode(14);
    head->next->next = new ListNode(21);
    head->next->next->next = new ListNode(28);

    // Assigning random pointers
    head->random = head->next->next; // 7 -> 21
    head->next->random = head; // 14 -> 7
    head->next->next->random = head->next->next->next; // 21 -> 28
    head->next->next->next->random = head->next; // 28 -> 14

    // Print the original linked list
    cout << "Original Linked List with Random Pointers:" << endl;
    printClonedLinkedList(head);

    // Clone the linked list
    Solution solution;
    ListNode* clonedList = solution.copyRandomList(head);

    // Print the cloned linked list
    cout << "\nCloned Linked List with Random Pointers:" << endl;
    printClonedLinkedList(clonedList);

    return 0;
}

Complexity Analysis:

• Time Complexity: O(2N) because the linked list is traversed twice, once for creating copies of each node and for the second time to set the next and random pointers for each copied node. The time to access the nodes in the map is O(1) due to hashing. Here N is the length of the Linked List.
• Space Complexity: O(N)+O(N) where N is the number of nodes in the linked list as all nodes are stored in the map to maintain mappings and the copied linked list takes O(N) space as well.

2️⃣ Optimal Approach

Intuition:

To avoid using extra space for mappings, insert each copied node right after its original node in the list. This allows quick access without additional storage.

Traverse the list to create a copy of each node and place it immediately after the original node. Then, set the random pointers for the copied nodes by using the copied nodes directly following the originals. Finally, separate the original and copied nodes by detaching alternate nodes, resulting in two lists: one with the original nodes and one with the copied nodes, both maintaining the original structure and random pointers.

Approach:

1. Traverse the original list and create a copy of each node, inserting it immediately after the original node. This way, each original node is followed by its copy.
2. Traverse the modified list and set the random pointers for the copied nodes to match the corresponding original nodes. If an original node’s random pointer is null, set the copied node’s random pointer to null as well.
3. Traverse the modified list again to separate the copied nodes from the original nodes. Break the links between the original and copied nodes, and restore the original list to its initial state by fixing the next pointers.
4. Return the head of the deep copy obtained after extracting the copied nodes from the modified list.

Code:

#include <bits/stdc++.h>
using namespace std;

// Definition of singly linked list
struct ListNode {
    int val;
    ListNode *next;
    ListNode *random;
    ListNode() {
        val = 0;
        next = NULL;
        random = NULL;
    }
    ListNode(int data1) {
        val = data1;
        next = NULL;
        random = NULL;
    }
    ListNode(int data1, ListNode *next1, ListNode* r) {
        val = data1;
        next = next1;
        random = r;
    }
};

class Solution {
public:
    // Insert a copy of each node in between the original nodes
    void insertCopyInBetween(ListNode* head) {
        ListNode* temp = head;
        while (temp != NULL) {
            ListNode* nextElement = temp->next;
            // Create a new node with the same data
            ListNode* copy = new ListNode(temp->val);
            
            copy->next = nextElement;
            
            temp->next = copy;
            
            temp = nextElement;
        }
    }

    // Function to connect random pointers of the copied nodes
    void connectRandomPointers(ListNode* head) {
        ListNode* temp = head;
        while (temp != NULL) {
            // Access the copied node
            ListNode* copyNode = temp->next;
            
            /*If the original node has a random pointer
            point the copied node's random to the 
            corresponding copied random node
            set the copied node's random to null 
            if the original random is null*/
            if (temp->random) {
                
                copyNode->random = temp->random->next;
            } else {
                
                copyNode->random = NULL;
            }
            
            // Move to next original node
            temp = temp->next->next;
        }
    }

    // Function to retrieve the deep copy of the linked list
    ListNode* getDeepCopyList(ListNode* head) {
        ListNode* temp = head;
        // Create a dummy node
        ListNode* dummyNode = new ListNode(-1);
        // Initialize a result pointer
        ListNode* res = dummyNode;

        while (temp != NULL) {
            /*Creating a new List by 
            pointing to copied nodes*/
            res->next = temp->next;
            res = res->next;

            /*Disconnect and revert back 
            to the initial state of the 
            original linked list*/
            temp->next = temp->next->next;
            temp = temp->next;
        }
        
        /*Return the deep copy 
        of the list starting 
        from the dummy node*/
        return dummyNode->next;
    }

    // Function to clone the linked list
    ListNode* copyRandomList(ListNode* head) {
        // If the original list is empty, return null
        if (!head) return nullptr;

        // Insert nodes in between
        insertCopyInBetween(head);
        // Connect random pointers
        connectRandomPointers(head);
        // Retrieve deep copy of inked list
        return getDeepCopyList(head);
    }
};

// Function to print the cloned linked list
void printClonedLinkedList(ListNode* head) {
    while (head != nullptr) {
        cout << "Data: " << head->val;
        if (head->random != nullptr) {
            cout << ", Random: " << head->random->val;
        } else {
            cout << ", Random: nullptr";
        }
        cout << endl;
        // Move to the next node
        head = head->next;
    }
}

int main() {
    // Example linked list: 7 -> 14 -> 21 -> 28
    ListNode* head = new ListNode(7);
    head->next = new ListNode(14);
    head->next->next = new ListNode(21);
    head->next->next->next = new ListNode(28);

    // Assigning random pointers
    head->random = head->next->next; // 7 -> 21
    head->next->random = head; // 14 -> 7
    head->next->next->random = head->next->next->next; // 21 -> 28
    head->next->next->next->random = head->next; // 28 -> 14

    // Print the original linked list
    cout << "Original Linked List with Random Pointers:" << endl;
    printClonedLinkedList(head);

    // Clone the linked list
    Solution solution;
    ListNode* clonedList = solution.copyRandomList(head);

    // Print the cloned linked list
    cout << "\nCloned Linked List with Random Pointers:" << endl;
    printClonedLinkedList(clonedList);

    return 0;
}

Complexity Analysis:

• Time Complexity: O(3N) where N is the number of nodes in the linked list:
  • First traversal to create copies of the nodes and insert them between the original nodes.
  • Second traversal to set the random pointers of the copied nodes to their corresponding copied nodes.
  • Third traversal to separate the copied nodes from the original nodes.
• Space Complexity: O(N) where N is the number of nodes in the linked list as the only extra space allocated is to create the copied list without creating any other additional data structures.