[力扣] 剑指 Offer 第二天 - 复杂链表的复制

作者：陈明勇

2022-11-16
广东
本文字数：1687 字
阅读完需：约 6 分钟

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

题目来源

来源：力扣（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 := head    for node != nil {        mp[node] = &Node{Val: node.Val}        node = node.Next    }    node = head    for 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 := head    for cur != nil {        tmp := &Node{Val:cur.Val}        tmp.Next = cur.Next        cur.Next = tmp        cur = tmp.Next    }
    cur = head    for cur != nil {        if cur.Random != nil {            cur.Next.Random = cur.Random.Next        }        cur = cur.Next.Next    }
    res := head.Next    for head != nil {        next := head.Next        if next != nil {        head.Next = next.Next        }        head = next    }    return res}

复制代码

执行结果

复杂度分析

时间复杂度：O(N)，遍历两次链表需要 O(N) 的时间复杂度。

空间复杂度：O(1)，创建的新节点所使用的变量使用常数大小的额外空间。

总结

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

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

发布于: 刚刚阅读数: 4

原文链接:【http://xie.infoq.cn/article/b3e66e0af7d59e82626e56169】。文章转载请联系作者。

陈明勇

关注

一个热爱技术，喜欢专研技术的程序员。 2021-10-20 加入

还未添加个人简介

发布

暂无评论

创作场景

[力扣] 剑指 Offer 第二天 - 复杂链表的复制

题目来源

题目描述

示例

示例 1

示例 2

示例 3

示例 4

题目解析

算法 1

代码实现

执行结果

复杂度分析

算法 2

代码实现

执行结果

复杂度分析

总结

陈明勇

评论