LeetCode：138. 随机链表的复制

这是一个经典的数据结构题，当做数据结构来学习。

1、哈希映射

需要注意的是，指针也能够当做unordered_map的键值，指针实际上是一个地址值，在unordered_map中，使用指针的实际内存地址值计算哈希函数，通过指针值来判断两个键值是否相等。

在第一次遇到这个问题时，最容易想到的方法自然是使用哈希表直接构造一模一样的。
遇到任何一个新结点直接构造，并用哈希表存储映射，然后依次遍历连接，每个遍历到的结点仅有可能被构造过，但不可能更新过next或random。

使用哈希表：

• 时间复杂度：$O(n)$，其中n是链表的长度
  • 依次遍历，每个节点被遍历一次，每个节点被构造一次，每个节点被插入到哈希表一次，每个节点本身以及其后继和随机指向都在哈希表中被查找一次，平均查找和插入的速度为$O(1)$
• 空间复杂度：$O(n)$，哈希表的空间
  

class Solution {
public:Node* copyRandomList(Node* head) {unordered_map<Node *,Node *> mp;for(Node * p = head; p != nullptr; p = p->next){Node * nw;if(mp.count(p) == 0) {nw = new Node(p->val);mp[p] = nw;}//不重复构造，每个遍历到的结点p都需要更新next 和 randomelse nw = mp[p];if(p->next){//是否有后继if(mp.count(p->next) == 0){//后继是否被构造过Node * nw_nex =  new Node(p->next->val); //如果没有的话，则构造并建立映射，连接后继mp[p->next] = nw_nex;nw->next = nw_nex;}else nw->next = mp[p->next];//有被构造过直接连接后继}if(p->random){if(mp.count(p->random) == 0){Node * nw_random =new Node(p->random->val);mp[p->random] = nw_random;nw->random = nw_random;}else nw->random = mp[p->random];}}return mp[head];}
};

• 当然直接遍历一次构建所有哈希映射，然后再连接会更简单，可以减少判断是否被构造过的情况，因为先建立之后一定被构造。
  • 这种方法只需要遍历两遍链表，每个结点进行一次哈希插入，以及进行其的后继和其随机指针进行一次哈希查找即可。

2、迭代 + 节点拆分（技巧性）

第一遍遍历：拷贝结点，并将拷贝出的结点作为原结点的后继，拷贝后的结点的后继指向原结点的原始后继;
第二遍遍历：更新random
第三遍遍历：节点拆分，将拷贝出的结点和原始节点拆出来变成俩链。

你会发现，将拷贝结点作为原结点的后继，拷贝后的结点的后继指向原结点的原始后继并不影响原链表的遍历，因此这个方法是可行的。

这个方法拷贝的思想相当于先拷贝后继，将其放入到原始节点的后继。这并不会导致无法实现原链表的任何功能。然后再更新拷贝后的结点的信息，这时更新时所有原始链表的结点都已经被拷贝过一次，所有信息都可以直接使用。而不需要像方法一一样，顺序遍历更新，并不一定能保证random已经被创建出来，因此只能用哈希表存储

• 时间复杂度：$O(n)$，n是链表长度
  • 遍历一遍链表，拆分一次链表
• 空间复杂度：$O(1)$
  

class Solution {
public:Node* copyRandomList(Node* head) {if(!head) return head;//拷贝结点，更新后继Node * cur = head;while(cur){Node * nextNode = cur->next;cur->next = new Node(cur->val);cur->next->next = nextNode;cur = nextNode;}//更新randomcur = head;while(cur){if(cur->random) cur->next->random = cur->random->next;//random可能为空cur = cur->next->next;}//节点拆分cur = head;Node * p = new Node(0);Node * result = p;while(cur){p->next = cur->next;p = p->next;cur->next = cur->next->next;cur = cur->next;}return result->next;}
};