LeetCode138 链表的深度拷贝

题目

给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。 要求返回这个链表的深拷贝。 示例： 输入： {“$id”:”1”,”next”:{“$id”:”2”,”next”:null,”random”:{“$ref”:”2”},”val”:2},”random”:{“$ref”:”2”},”val”:1} 解释： 节点 1 的值是 1，它的下一个指针和随机指针都指向节点 2 。 节点 2 的值是 2，它的下一个指针指向 null，随机指针指向它自己。

这个题目有一定难度的，难度在于随机指针。这个指针域该怎么复制是一个很重要的问题。 深度拷贝：原链表和新链表不互相影响，可以随意更改。 这个题目可以用 map 来计算，主要是存储随机指针之间的逻辑关系，map 中存储的是地址和节点 ID 的映射。 难点有两点： 1.随机指针指向了哪一个节点？ 2.这个节点的地址是多少？ 而用 map 就是为了解决这两点的。

我自己的思路：首先存储随机指针指向的 ID，然后新建新的指针，顺便保存值和指针以及随机指针三个参数，返回新的指针。

写代码发现行不通，不知道该怎么写，存储随机指针以及保存其他的指针都好写，但是怎么新建新指针和将新指针的 next 域、random 域和原来的联系起来，这里不知道怎么写。

这里我的思路是有问题的，原因是我没有想清楚该做什么。我的思路是保存随机指针指向的 ID，这一步保存 ID 是对的，但是随机指针不对，这里保存的应该是新链表中的指针，而不是旧链表，同理，新建新的指针时，值可以保存，但是 next 指针和随机指针不能一次性保存的。

正确的方法，应该是，根据原链表的长度建立新链表，仅仅将值域的值赋值，next 域和 random 域暂时不用管，并且将新节点存放到 vector 中，然后保存旧节点的地址对应的 id。

然后再次遍历旧节点，连接新节点的 next 域，然后由于 map 中保存的是旧节点的地址，所以对旧节点的 random 域取地址，该地址一定在 map 中，且对应的 key 值即为指向的 id，结合该 id 在 vector 中索引，即可得到新节点中的 random 指针的地址。 最终代码如下：

Node* copyRandomList(Node* head)
{
	std::map<Node*, int > node_map;
	std::vector<Node*> node_vec;
	Node* ptr = head;
	int i = 0;
	while (ptr)
	{
		node_vec.push_back(new Node(ptr->val));
		//记录ptr 和ID的映射
		node_map[ptr] = i++;
		ptr = ptr->next;
	}

	node_vec.push_back(0);
	ptr = head;
	i = 0;
	while (ptr)
	{
		node_vec[i]->next = node_vec[i + 1];
		if (ptr->random!=NULL)
		{
			int id = node_map[ptr->random];//get ID
			node_vec[i]->random = node_vec[id];
		}
		ptr = ptr->next;
		i++;
	}
	return node_vec[0];
}