我觉得 LeetCode 的 Acceptance 排行不仅仅和难度有关，更和题意表述是否清晰有关。这道题正好是第 100 道，颇有纪念价值。但遗憾的是，题目依旧是表述不清。

表述让人困惑，应该辅之以示例，但 LeetCode 的第二个特点便是，无示例的代码，往往便会表述产生歧义。两者相辅相成，相映成趣。

以上是在 100 斩之后对 LeetCode 的一点吐槽。

此题创造了一种新的数据结构（意思是此前的题目里未曾出现过），然后引出一个工程上比较常用的概念：deep copy. 这里不深究 deep copy 与 shallow copy 的区别，只需要知道所谓 deep copy，就是 copy 出来的副本与原本是完全独立，互不影响的。你删掉原来的，不会影响副本，反之亦然。

Ok, 这道题就是让你 deep copy 一个新奇的单链表。

为了效率考虑，我还是希望在一次迭代中 finish the work. 但困难在于，random 指针能指向原链表的任意节点，若我从头组建新链表的话，random 指向的原节点，很有可能在新链表中没有对应。

解决这个困难，有两种思路：

分成两步迭代，第一步，拷全原链表中所有元素；第二步，建立 random 体系。
坚持一步迭代，遇到 random 指向的节点，就立刻创建，迭代过程中如果遇到已经创建过的节点，则跳过。

第一种思路，清晰简单，不做解释。对于第二种，如果我们想实现"立刻创建"，且不会丢失创建的这个独立节点，我们必须要有一套索引系统。

而 HashMap 是天然的索引系统。用它来协助我们记录 random 体系，再好不过了。

让我们初始化一个 HashMap: unordered_map<RandomListNode*, RandomListNode*>, Key 是原链表节点，Value 是副本节点。一一对应。然后开始迭代原链表(head 持续后移)：

若 hashmap[head] == NULL, 表示新节点还未创建，创建之。
hashmap[head] 存在，则连接副本节点的前后关系（next 关系）
若 head->random && hashmap[head->random] == NULL, 表示 random 指向的节点在副本链表中还未创建，创建之。
hashmap[head->random] 存在，则链接副本节点的 random 关系。
后移 head, 以及新链表的指针（如代码中的 next 指针），进行下一次迭代。

最后返回 hashmap 中第一个 value 即可。

有一个小细节是链表题常用的，就是建立一个用于索引的头节点 preHead，返回时，仅需返回 preHead.next 即可。

AC 后发现效率并不高，排行甚至快接近 Python 的速度了。（中下档）

但因为咱们从算法复杂度上讲，时间和空间都是真正的 O(N)，消耗可能是花在 unordered_map 上了，有点不解。若有知道的童鞋，望能帮我解惑，不胜感激。