(LeetCode 面试经典 150 题) 138. 随机链表的复制 (哈希表)

思路：哈希表，时间复杂度0(n)。

C++版本：

/*
// 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:unordered_map<Node *,Node *> mp;Node* copyRandomList(Node* head) {if(head==nullptr) return head;if(!mp.count(head)){Node *tmp= new Node(head->val);mp[head]=tmp;// 注意，在递归前，要先用哈希表记录tmptmp->next=copyRandomList(head->next);tmp->random=copyRandomList(head->random);}return mp[head];}
};

JAVA版本：

/*
// Definition for a Node.
class Node {int val;Node next;Node random;public Node(int val) {this.val = val;this.next = null;this.random = null;}
}
*/class Solution {Map<Node,Node> mp=new HashMap<>();public Node copyRandomList(Node head) {if(head==null) return head;if(!mp.containsKey(head)){Node tmp=new Node(head.val);mp.put(head,tmp);tmp.next=copyRandomList(head.next);tmp.random=copyRandomList(head.random);}return mp.get(head);}
}

GO版本：

/*** Definition for a Node.* type Node struct {*     Val int*     Next *Node*     Random *Node* }*/
var mp map[*Node]*Node =map[*Node]*Node{}
func copyRandomList(head *Node) *Node {if head ==nil {return head}if x,ok :=mp[head]; ok{return x}tmp := &Node{ Val:head.Val }mp[head]=tmptmp.Next=copyRandomList(head.Next)tmp.Random=copyRandomList(head.Random)return tmp
}