链表深拷贝

在 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
}

公众号：没有梦想的阿巧 后台回复 "群聊"，一起学习，一起进步