题目

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

示例 1：

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

示例 2：

输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]

示例 3：

输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]

示例 4：

输入：head = []
输出：[]
解释：给定的链表为空（空指针），因此返回 null。

题解

本题需要对一个特殊的链表进行深拷贝，相比于普通链表，每个元素都有一个随机指针，指向链表中的某个元素。

思路一（hash表）

构建一个hash表，记录源节点和拷贝节点的映射

• 遍历链表，生成记录源节点和拷贝节点的映射的hash表
• 再次遍历链表，根据源节点的next，更新对应拷贝节点的next；根据源节点的random，更新对应拷贝节点的random

思路二（拼接拆分）

不使用hash表，而是将拷贝节点插入源节点之后，通过源节点的next作为映射

• 遍历链表，源节点之后插入拷贝节点
• 以步进为2遍历链表，复制random关系；此时node.Next即为拷贝节点，拷贝节点的random即为node.Random.Next
• 以步进为2遍历链表，拆分源节点和拷贝节点

代码

hash表

func copyRandomList(head *Node) *Node {
	if head == nil {
		return nil
	}

	cur := head
	hash := make(map[*Node]*Node)

	// 构造源节点=>拷贝节点映射
	for cur != nil {
		hash[cur] = &Node{
			Val: cur.Val,
		}
		cur = cur.Next
	}

	cur = head
	for cur != nil {
		// 更新拷贝节点next和random
		hash[cur].Next = hash[cur.Next]
		hash[cur].Random = hash[cur.Random]
		cur = cur.Next
	}

	return hash[head]
}

拼接拆分

func copyRandomList2(head *Node) *Node {
	if head == nil {
		return head
	}
	// 插入拷贝节点
	for node := head; node != nil; node = node.Next.Next {
		node.Next = &Node{Val: node.Val, Next: node.Next}
	}
	// 更新拷贝节点random
	for node := head; node != nil; node = node.Next.Next {
		if node.Random != nil {
			node.Next.Random = node.Random.Next
		}
	}
	// 拆分链表
	newHead := head.Next
	for node := head; node != nil; node = node.Next {
		newNode := node.Next
		node.Next = node.Next.Next
		if newNode.Next != nil {
			newNode.Next = newNode.Next.Next
		}
	}
	return newHead
}