随机链表的复制(哈希表)

主要问题就是如何让新的链表节点的random指向新的结点。直接用哈希，将旧的结点与新的节点存储为哈希表，在生成新链表时记录对应关系。到后面一起遍历两个链表，利用哈希表找到对应的random结点：

/* // 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) { unordered_map<Node*,Node*> nm; Node* copytail=NULL; Node* copyhead=NULL; Node* cur=head; while(cur){ Node* copy=new Node(cur->val); if(copyhead==NULL){ copyhead=copytail=copy; } else{ copytail->next=copy; copytail=copy; } nm[cur]=copy; cur=cur->next; } cur=copyhead; Node* cur1=head; while(cur){ cur->random=nm[cur1->random]; cur=cur->next; cur1=cur1->next; } return copyhead; } };

通过unordered_map存储节点对应关系，确保了random指针的正确指向。关键点在于利用哈希表保存原始节点与拷贝节点的映射，从而在第二次遍历时快速查找对应的random节点。