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 和 random
            else 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;
		}
		//更新random
		cur = 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;
    }
};