哈希表
/**
* Definition for singly-linked list with a random pointer.
* struct ListNode {
* int val;
* ListNode *next, *random;
* ListNode(int x) : val(x), next(NULL), random(NULL) {}
* };
*/
class Solution {
public:
ListNode *copyRandomList(ListNode *head) {
unordered_map<ListNode*, ListNode*> hash;
ListNode* newList = new ListNode(-1);
auto nextNode = newList;
for (auto node = head; node; node = node->next) {
ListNode* newNode = new ListNode(node->val);
nextNode->next = newNode;
hash.insert({node, newNode});
nextNode = nextNode->next;
}
for (auto node = head; node; node = node->next) {
if (node->random) {
auto curNode = hash[node];
// 这里不太好理解
curNode->random = hash[node->random];
}
}
return newList->next;
}
};