Lecture 144:-Copy List with Random Pointer

Copying a linked list with random pointers involves creating a new linked list where each node's next pointer is connected to a new node with the same data, and each node's random pointer is also updated to point to the corresponding node in the new list.

Here's a step-by-step approach:

1. Traverse the original list and create a new node for each node in the original list. Set the next pointer of the new node to the next node in the original list.

2. Traverse the original list again. For each node in the original list, update the corresponding new node's random pointer to point to the new node that corresponds to the random pointer's target in the original list.

3. Separate the original list and the new list. The next pointers of the nodes in the new list will be the desired result.

Here's a C++ implementation of copying a linked list with random pointers:

cppCopy code

#include <iostream> #include <unordered_map> class Node { public: int data; Node* next; Node* random; Node(int value) : data(value), next(nullptr), random(nullptr) {} }; Node* copyRandomList(Node* head) { if (!head) return nullptr; std::unordered_map<Node*, Node*> nodeMap; // Step 1: Create new nodes with next pointers Node* current = head; while (current) { nodeMap[current] = new Node(current->data); current = current->next; } // Step 2: Update random pointers current = head; while (current) { nodeMap[current]->next = nodeMap[current->next]; nodeMap[current]->random = nodeMap[current->random]; current = current->next; } return nodeMap[head]; } void displayListWithRandom(Node* head) { Node* current = head; while (current) { std::cout << "Data: " << current->data; if (current->random) std::cout << ", Random: " << current->random->data; std::cout << std::endl; current = current->next; } } int main() { Node* head = new Node(1); head->next = new Node(2); head->next->next = new Node(3); head->next->next->next = new Node(4); head->random = head->next->next; // 1 -> 3 head->next->random = head; // 2 -> 1 head->next->next->random = head->next; // 3 -> 2 head->next->next->next->random = head->next->next; // 4 -> 3 std::cout << "Original List with Random Pointers:" << std::endl; displayListWithRandom(head); Node* copiedHead = copyRandomList(head); std::cout << "Copied List with Random Pointers:" << std::endl; displayListWithRandom(copiedHead); return 0; }

In this example, the copyRandomList function creates a new linked list with the same data and updates the next and random pointers accordingly. The displayListWithRandom function is used to display the original and copied lists along with their random pointers.

The time complexity of copying a linked list with random pointers using this approach is O(n), where n is the number of nodes in the list. The space complexity is also O(n) due to the additional space used for the hash map.