首页 > 代码库 > Copy List with Random Pointer
Copy List with Random Pointer
A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.
Return a deep copy of the list.
思路：本题要求复制链表，因为每个元素存在一个随机指针，所以使问题变得稍微复杂一些。
方法1：首先，遍历链表，复制当前节点，并将当前节点的地址和新节点的地址映射存入map中；然后，再次遍历链表，通过查找map，找到当前节点及其next和random指针对应的新节点的地址，并修改当前节点对应新节点的next和random字段。
1 class Solution { 2 public: 3 RandomListNode *copyRandomList( RandomListNode *head ) { 4 if( !head ) { return 0; } 5 unordered_map<RandomListNode*,RandomListNode*> addrMap; 6 RandomListNode *curr = head; 7 while( curr ) { 8 addrMap[curr] = new RandomListNode( curr->label ); 9 curr = curr->next;10 }11 curr = head;12 while( curr ) {13 RandomListNode *newCurr = addrMap[curr];14 if( curr->next ) { newCurr->next = addrMap[curr->next]; }15 if( curr->random ) { newCurr->random = addrMap[curr->random]; }16 curr = curr->next;17 }18 return addrMap[head];19 }20 };
上述方法为完成复制，对每个节点可能需要对map进行3次查找。
方法2：与方法1类似，也使用map记录原始节点和新节点的地址映射关系。不同之处在于，第一次遍历时，已经完成了对正常链表的复制，但新节点的random字段与原始节点相同。因此，第二次遍历时，通过查找map修改新节点的random字段。
1 class Solution { 2 public: 3 RandomListNode *copyRandomList( RandomListNode *head ) { 4 if( head == 0 ) { return 0; } 5 map<RandomListNode*,RandomListNode*> addrMap; 6 RandomListNode *newhead = new RandomListNode(head->label), *node = newhead; 7 node->random = head->random; addrMap[head] = node; 8 while( head->next ) { 9 head = head->next;10 node->next = new RandomListNode(head->label);11 node = node->next;12 node->random = head->random;13 addrMap[head] = node;14 }15 node = newhead;16 while( node ) {17 if( node->random ) {18 node->random = addrMap[node->random];19 }20 node = node->next;21 }22 return newhead;23 }24 };
该方法相比方法1，对每个节点只需要对map进行1次查找。但其第一次遍历的循环体较方法1要复杂。方法1和方法2都需要使用map记录原始节点和新节点的地址映射。
方法3：通过三次遍历，完成复制过程，不需要使用map存储地址映射关系。
第一次遍历，通过将原始节点的random字段指向新节点的地址，同时将其random字段的原始值存储在新节点的label字段中，以实现原始节点和新节点的映射。这使得我们可以通过原始节点的random字段找到其对应的新节点，这与使用map建立地址映射关系作用相同。
第二次遍历，通过上述映射关系，修改新节点的random字段和next字段，使其指向对应的新节点。
第三次遍历，修改新节点的label字段，同时恢复原始节点的random字段。
1 class Solution { 2 public: 3 RandomListNode *copyRandomList( RandomListNode *head ) { 4 if( head == 0 ) { return 0; } 5 RandomListNode *node = head; 6 // first loop: new all nodes. 7 while( node ) { 8 RandomListNode *newNode = new RandomListNode( (int)node->random ); 9 node->random = newNode;10 node = node->next;11 }12 // second loop: assign random and next pointer.13 node = head;14 while( node ) {15 RandomListNode *newNode = node->random;16 RandomListNode *random = (RandomListNode*)newNode->label;17 if( random ) {18 newNode->random = random->random;19 }20 if( node->next ) {21 newNode->next = node->next->random;22 }23 node = node->next;24 }25 // third loop: recover ramdom pointer and copy label.26 node = head;27 RandomListNode *newHead = head->random;28 while( node ) {29 RandomListNode *newNode = node->random;30 node->random = (RandomListNode*)newNode->label;31 newNode->label = node->label;32 node = node->next;33 }34 return newHead;35 }36 };