题目描述#

给你一个长度为 n 的链表，每个节点除了 next 指针之外，还有一个额外的 random 指针。这个指针可以指向链表中的任意节点，也可以是 nil。

现在需要构造这个链表的深拷贝。新链表中的每个节点都要重新创建，节点值与原节点一致，同时 next 和 random 的指向关系也要和原链表保持一致，并且不能再指向原链表中的任何节点。

思路#

这份代码的核心做法是用一个哈希表记录“原节点”和“新节点”的对应关系。因为 random 指针可能随时指向链表中的任意位置，如果只顺着 next 去复制，很难在第一次遇到某个节点时就立刻把所有引用关系都补完整，所以先把节点映射建立起来会更直接。

第一遍遍历只做一件事：为原链表中的每个节点创建一个新的节点，并存进 nodeMap。这样哈希表里就有了完整的“旧节点 -> 新节点”映射。

第二遍遍历再去补指针关系。对于当前原节点 cur，它对应的新节点就是 nodeMap[cur]，那么新节点的 Next 应该指向 nodeMap[cur.Next]，Random 应该指向 nodeMap[cur.Random]。由于 Go 中从 map 读取一个不存在的键会拿到零值，所以当 cur.Next 或 cur.Random 为 nil 时，这里也会自然得到 nil，刚好符合题意。

整个过程遍历链表两次，时间复杂度是 O(n)，额外使用一个哈希表保存映射，空间复杂度也是 O(n)。

代码#

/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Next *Node
 *     Random *Node
 * }
 */

func copyRandomList(head *Node) *Node {
	nodeMap := make(map[*Node]*Node)
	cur := head

	// 第一遍循环
	for cur != nil {
		nodeMap[cur] = &Node{Val: cur.Val}
		cur = cur.Next
	}
	cur = head
	// 第二遍循环
	for cur != nil {
		nodeMap[cur].Next = nodeMap[cur.Next]
		nodeMap[cur].Random = nodeMap[cur.Random]
		cur = cur.Next
	}

	return nodeMap[head]
}