在 leetcode 上做到了一道题，让返回一个链表的深拷贝，感觉很有意思，记录一下。
深拷贝和浅拷贝
什么是浅拷贝？当你在拷贝一种数据结构的时候（结构体、类、map...），如果拷贝的只是这个数据结构的引用，那么这就是浅拷贝
举个例子（浅拷贝)
此时有一个 map，暂且命名为 "s"，存放一个 1
s := make(map[int]int, 0)
s[1] = 1
将 "s" 拷贝给 map "p"，修改 p 的值
p[1] = 2
分别打印出修改前和修改后 "s" 里存的值，看看是什么效果。
s := make(map[int]int, 0)
s[1] = 1
fmt.Println(s)
p := s
p[1] = 2
fmt.Println(s)
输出
map[1:1]
map[1:2]
修改 p 的值，但是 s 里的值也发生了变化，这说明 s 和 p 实际上都是指向的同一块内存地址，也就是说，在拷贝 s 到 p 的时候，其实只是拷贝了一个指针，这就是浅拷贝。
深拷贝
和浅拷贝与之相对应的就是深拷贝，深拷贝就不是只拷贝一个指针，而是要拷贝指针指向的内存中的所有数据，对于 map 的拷贝，流行的做法都是通过序列化和反序列化来做。
看题
来看一下这道题目
给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。
要求返回这个链表的?深拷贝。?
我们用一个由?n?个节点组成的链表来表示输入/输出中的链表。每个节点用一个?[val, random_index]?表示：
val：一个表示?Node.val?的整数。
random_index：随机指针指向的节点索引（范围从?0?到?n-1）；如果不指向任何节点，则为??null?。
示例1
输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
思考
- 拷贝一个链表，如果没有 random 指针，那就简单了，就是最基础的遍历一次链表，然后创建节点值就行。
- 如果不要求深拷贝，可以在创建链表的时候把原链表的 random 指针直接赋给新链表。
偏偏是两个要求都有，这就有点伤脑了，主要是要想办法保存每一个节点的 random 指针指向的位置，在创建新链表的时候，相对应的指针也要指向相对的位置。
我在这里只记录一种解法：将每个节点的克隆链接到对应节点的后面，使得新旧链表交替连接，处理 random 指针之后再把两个链表分开。
链接之后应当是这样。
处理 random 指针。
此时 random 已经指向了正确的位置，只需要将两个链表分开就行。
golang 完整实现
func copyRandomList(head *Node) *Node {
if head == nil {
return head
}
// 复制节点，紧挨到到后面
// 1->2->3 ==> 1->1'->2->2'->3->3'
cur := head
for cur != nil {
clone := &Node{Val: cur.Val, Next: cur.Next}
temp := cur.Next
cur.Next = clone
cur = temp
}
// 处理random指针
cur = head
for cur != nil {
if cur.Random != nil {
cur.Next.Random = cur.Random.Next
}
cur = cur.Next.Next
}
// 分离两个链表
cur = head
cloneHead := cur.Next
for cur != nil && cur.Next != nil {
temp := cur.Next
cur.Next = cur.Next.Next
cur = temp
}
// 原始链表头：head 1->2->3
// 克隆的链表头：cloneHead 1'->2'->3'
return cloneHead
}
公众号：没有梦想的阿巧 后台回复 "群聊"，一起学习，一起进步
有疑问加站长微信联系（非本文作者）
