[数据结构与算法]剑指 Offer 35. 复杂链表的复制

剑指 Offer 35. 复杂链表的复制

请实现 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。
?

提示：

-10000 <= Node.val <= 10000
Node.random?为空（null）或指向链表中的节点。
节点数目不超过 1000 。
?

注意：本题与主站 138 题相同：https://leetcode-cn.com/problems/copy-list-with-random-pointer/

思路：见代码?

时间复杂度：O(n)，两轮遍历链表，时间复杂度与常系数无关，即：O(n) + O(n) = O(n)?

空件复杂度：哈希表 map?使用线性大小的额外空间

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

func copyRandomList(head *Node) *Node {
	// 方法1：
	// nodeMap := make(map[*Node]*Node)
	// for cur := head; cur != nil; cur = cur.Next {
	// 	nodeMap[cur] = &Node{ /*cur.Val, nil, nil*/ } // 首先构建每个单节点，赋值其Val，并初始化map
	// }
	
	// // 之所以用两个循环，就是为了好懂，其实理论上1个循环也是可以的
	// for cur := head; cur != nil; cur = cur.Next {
	// 	nodeMap[cur].Val, nodeMap[cur].Next, nodeMap[cur].Random = cur.Val, nodeMap[cur.Next], nodeMap[cur.Random] // ok 连接各个单节点的Next和Random
	// }
	// return nodeMap[head]

	// 方法2：
	nodeMap := make(map[*Node]*Node)
	for cur := head; cur != nil; cur = cur.Next {
		nodeMap[cur] = &Node{cur.Val, nil, nil} // 首先构建每个单节点，赋值其Val，并初始化map
	}

	// 之所以用两个循环，就是为了好懂，其实理论上1个循环也是可以的
	for cur := head; cur != nil; cur = cur.Next {
		// nodeMap[cur] = &Node{Val: cur.Val, Next: cur.Next, Random: cur.Random} // 错误，要取map中的Next
		// nodeMap[cur] = &Node{Next: nodeMap[cur.Next], Random: nodeMap[cur.Random]} // 错误 ??? 为什么这样写不行
		nodeMap[cur].Next, nodeMap[cur].Random = nodeMap[cur.Next], nodeMap[cur.Random] // ok 连接各个单节点的Next和Random
	}
	return nodeMap[head]
}