138. Copy linked list with random pointer

Given a linked list, each node contains an additional random pointer that can point to any node in the linked list or to an empty node.

Ask to return a deep copy of this linked list.

A deep copy means that the source object and the copied object are independent of each other, and changes to either object will not affect the other object. Before performing the assignment, create a separate memory space for the data member of the pointer type to realize the copy of the real content.

We use a linked list of n nodes to represent a linked list in input/output. Each node is represented by a [val, random_index]:

val: An integer representing Node.val.

random_index: The index of the node pointed to by the random pointer (ranging from 0 to n-1); null if it does not point to any node.

Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]

Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]

Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]

Ideas:

1. Traverse the linked list starting from the head node. First create a new head copy node, and put the reference of this new node into the visited dictionary as well.

2.random pointer

If the random pointer of the current node i points to a node j and the node j has been copied, we will directly use the reference of the node in the visited dictionary without creating a new node.

If the node j pointed to by the random pointer of the current node i has not been copied, we create a corresponding new node for the j node and put it into the visited node dictionary.

3.next pointer

If the node j pointed to by the next pointer of the current node i has a copy in the visited dictionary, we directly use its copy node.

If the node j pointed to by the next pointer of the current node i has not been visited yet, we create a copy of the corresponding node and put it into the visited dictionary.

If the node j pointed to by the next pointer of the current node i has not been visited yet, we create a copy of the corresponding node and put it into the visited dictionary.

4. We repeat steps 2 and 3 until we reach the end of the linked list.

Time complexity o(n), space complexity o(n).

Code:

/* // Definition for a Node. class Node { public: int val; Node* next; Node* random; Node(int _val) { val = _val; next = NULL; random = NULL; } }; */ class Solution { public: Node* copyRandomList(Node* head) { Node *old_node, *new_node, *head_new; if(!head) return head; unordered_map<Node*,Node*> m; old_node = head; new_node = new Node(old_node->val); m[old_node] = new_node; head_new = new_node; while(old_node) { if(old_node->random) new_node->random = copy(m, old_node->random); if(old_node->next) new_node->next = copy(m, old_node->next); old_node = old_node->next; new_node = new_node->next; } return head_new; } Node *copy(unordered_map<Node*, Node*> &m, Node *old_node1) { unordered_map<Node*, Node*>::iterator it = m.find(old_node1); Node *new_node1; if(it!=m.end()) { return it->second; } else { new_node1 = new Node(old_node1->val); m[old_node1] = new_node1; return new_node1; } } };

Ideas:

1. Traverse the original linked list and copy each node, place the copied node next to the original node, and create a linked list in which the old node and the new node are interleaved.

2. Iterate over the linked list with the old and new nodes interleaved, and use the random pointer of the old node to update the random pointer corresponding to the new node. Let's say B 's random pointer points to A , which means that B' 's random pointer points to A' .

3. Now that the random pointer has been assigned to the correct node, the next pointer also needs to be assigned correctly in order to link the new node correctly and relink the old node correctly. That is, split the old and new linked lists.

Code:

/* // Definition for a Node. class Node { public: int val; Node* next; Node* random; Node(int _val) { val = _val; next = NULL; random = NULL; } }; */ class Solution { public: Node* copyRandomList(Node* head) { if(head==NULL) return head; Node *old_node, *new_node, *new_head; old_node = head; while(old_node) { new_node = new Node(old_node->val); new_node->next = old_node->next; old_node->next = new_node; old_node = new_node->next; } old_node = head; while(old_node) { new_node = old_node->next; if(old_node->random) new_node->random = old_node->random->next; old_node = old_node->next->next; } old_node = head; new_node = head->next; new_head = new_node; while(old_node) { old_node->next = old_node->next->next; if(new_node->next) new_node->next = new_node->next->next; old_node = old_node->next; new_node = new_node->next; } return new_head; } };