关于golang:链表深拷贝

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

公众号：没有幻想的阿巧 后盾回复 “ 群聊 ”，一起学习，一起提高