这里写目录标题

• 题目来源
• 题目描述
• 示例
• • 示例 1
  • 示例 2
  • 示例 3
  • 示例 4
• 题目解析
• 算法 1
• • 代码实现
  • 执行结果
  • 复杂度分析
• 算法 2
• • 代码实现
  • 执行结果
  • 复杂度分析
• 总结

耐心和持久胜过激烈和狂热。

题目来源

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/fu-za-lian-biao-de-fu-zhi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目描述

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

题目解析

如果是普通的链表，我们完全可以遍历链表的过程中复制一个链表，但是复杂链表中存在随机指针，如果是按照原始的方式去拷贝，会存在随机节点没有创建的问题，因此拷贝的前提是【所有节点都已被创建】。既能创建新节点，又能将原节点与新节点一一对应，我们可以使用哈希表去实现。

算法 1

本题是基于 Go 语言去实现

• 定义一个 map，存储结构 → key 为原节点，value 为新节点，初始化 node 指向头结点
• 遍历链表，将原节点和新节点存入 map → 键值对(原节点 : 新节点)
• node 再次指向头结点，再次遍历链表，构建新节点的 next 引用指向和 random 引用指向
• 返回新节点的头结点

代码实现

/*** Definition for a Node.* type Node struct {*     Val int*     Next *Node*     Random *Node* }*/func copyRandomList(head *Node) *Node {mp := make(map[*Node]*Node)node := headfor node != nil {mp[node] = &Node{Val: node.Val}node = node.Next}node = headfor node != nil {mp[node].Next = mp[node.Next]mp[node].Random = mp[node.Random]node = node.Next}return mp[head]    
}

执行结果

复杂度分析

时间复杂度：O(N)，遍历两次链表需要 O(N) 的时间复杂度。
空间复杂度：O(N)，其中 N 是链表的长度，为哈希表的额外空间开销。

算法 2

算法优化，遍历链表是无可避免的，因此我们可以从空间的维度去优化 → 去除哈希表的使用。使用另外一种方式，在原链表中做映射关系。
原链表
A → B → C → D
映射之后的链表
A → A' → B → B' → C → C' → D → D'
步骤：

• 判断头结点是否为空，条件成立则直接返回头结点
• 定义新指针 cur 指向头结点，遍历 cur 链表，创建新节点并由原节点的 next 节点指向新节点，做映射关系，然后调节指向。
• cur 重新指向头结点，遍历 cur 链表，构建 ramdom 引用指向，新节点的 random 指向原节点 random 的 next 节点（新 copy 的节点）
• 最后拆分新旧节点，返回新头结点

代码实现

/*** Definition for a Node.* type Node struct {*     Val int*     Next *Node*     Random *Node* }*/func copyRandomList(head *Node) *Node {if head == nil {return nil}cur := headfor cur != nil {tmp := &Node{Val:cur.Val}tmp.Next = cur.Nextcur.Next = tmpcur = tmp.Next}cur = headfor cur != nil {if cur.Random != nil {cur.Next.Random = cur.Random.Next}cur = cur.Next.Next}res := head.Nextfor head != nil {next := head.Nextif next != nil {head.Next = next.Next}head = next}return res
}

执行结果

复杂度分析

时间复杂度：O(N)，遍历两次链表需要 O(N) 的时间复杂度。
空间复杂度：O(1)，创建的新节点所使用的变量使用常数大小的额外空间。

总结

第一种算法使用了 map 结构去实现新旧节点映射，而第二种则以一条线穿插着新旧节点，然后在这条线上构建 copy 后的链表，非常巧妙。

如果本文对你有帮助，欢迎点赞收藏加关注，如果本文有错误的地方，欢迎指正！