脚本宝典收集整理的这篇文章主要介绍了138 复制带随机指针的链表，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。
刚刚看题目会有点不适的题，因为要根据随机链表的结构来实现重构一个新的链表。后来就想明白了，可以通过map来实现新表与旧表的一一对应的关系。搭建基础的结构的同时，同时建立新旧链表对应节点的一一对应的关系，从旧的节点可以找到新的节点。从而再一次遍历链表，用双指针同时指向两个链表对应位置，对于遍历到的每个节点，取旧节点的random节点，然后将该节点一一对应的节点作为新节点的random节点。完成遍历则完成任务，贴代码
1 /* 2 // DefinITion for a Node. 3 class Node { 4 public: 5 int val; 6 Node* next; 7 Node* random; 8 9 Node(int _val) { 10 val = _val; 11 next = NULL; 12 random = NULL; 13 } 14 }; 15 */ 16 17 class Solution { 18 public: 19 Node* copyRandoMList(Node* head) 20 { 21 if(!head) 22 return NULL; 23 Node* temp = head->next; 24 Node* newNode = new Node(head->val); 25 Node* newHead = newNode; 26 map<Node*,Node*> contra; 27 //用Map建立原始链表与新链表一一对应的关系 28 contra.insert(pair<Node*,Node*>(head,newHead)); 29 //首先完成不包含随机指针的深拷贝 30 while(temp!=NULL) 31 { 32 newNode->next = new Node(temp->val); 33 newNode = newNode->next; 34 contra.insert(pair<Node*,Node*>(temp,newNode)); 35 temp = temp->next; 36 } 37 temp = head; 38 newNode = newHead; 39 //通过map来建立random 40 while(temp!=NULL) 41 { 42 newNode->random = contra[temp->random]; 43 temp = temp->next; 44 newNode = newNode->next; 45 } 46 return newHead; 47 } 48 };
有一种使用递归的方法，本质思想也是建立新旧节点的对应关系。该方法的巧妙在于深拷贝当前节点之后，该节点的next指针与random指针交给递归函数去完成。在递归的过程中若是遇到之前已经完成建立的就返回哈希表中的对应项即可。贴代码
1 /* 2 // Definition for a Node. 3 class Node { 4 public: 5 int val; 6 Node* next; 7 Node* random; 8 9 Node(int _val) { 10 val = _val; 11 next = NULL; 12 random = NULL; 13 } 14 }; 15 */ 16 17 class Solution { 18 public: 19 unordered_map<Node*,Node*> cachedNode; 20 Node* copyRandomList(Node* head) 21 { 22 if(!head) 23 return NULL; 24 else 25 { 26 if(!cachedNode.count(head)) 27 { 28 Node* headNew = new Node(head->val); 29 cachedNode[head] = headNew; 30 headNew->next = copyRandomList(head->next); 31 headNew->random = copyRandomList(head->random); 32 } 33 return cachedNode[head]; 34 } 35 } 36 };
还有一种思路，基于迭代，就是将原链表的随机节点设置为深拷贝的复制节点，从而省去了哈希表的空间，代码是类似的，不贴了。
以上是脚本宝典为你收集整理的138 复制带随机指针的链表全部内容，希望文章能够帮你解决138 复制带随机指针的链表所遇到的问题。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。