写点什么

每日一题:LeetCode-138. 随机链表的复制

作者:半亩房顶
  • 2024-01-23
    北京
  • 本文字数:1101 字

    阅读完需:约 4 分钟

每日一题:LeetCode-138. 随机链表的复制

刷题使我快乐,满脸开心.jpg



题目

给你一个长度为 n 的链表,每个节点包含一个额外增加的随机指针 random ,该指针可以指向链表中的任何节点或空节点。


构造这个链表的 深拷贝。 深拷贝应该正好由 n全新 节点组成,其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点,并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。


例如,如果原链表中有 XY 两个节点,其中 X.random --> Y 。那么在复制链表中对应的两个节点 xy ,同样有 x.random --> y


返回复制链表的头节点。


用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示:


  • val:一个表示 Node.val 的整数。

  • random_index:随机指针指向的节点索引(范围从 0n-1);如果不指向任何节点,则为 null 。你的代码 接受原链表的头节点 head 作为传入参数。


示例 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]]
复制代码


提示:


  • 0 <= n <= 1000

  • -104 <= Node.val <= 104

  • Node.randomnull 或指向链表中的节点。

思路

思路应该是比较好想的,既然需要全复制,且可能存在环,那就用一个映射map来存储下所有的节点及其对应节点


  • 当重复之时直接返回

  • 没有对应节点则新建一个

  • 空节点直接返回空就好了


不过有一个小细节需要注意,在有环存在时,进入递归调用之前需要将新建的节点保存进去,否则会绕不出去导致内存溢出。

代码

func copyRandomList(head *Node) *Node {    cacheNodeMap := make(map[*Node]*Node, 0)    var deepCopy func(node *Node) *Node    deepCopy = func(node *Node) *Node {        if node == nil {            return nil        }        if temp, ok := cacheNodeMap[node]; ok {            return temp        }        newNode := &Node{Val: node.Val}        // 注意 放入map 跟 求解next和random 的顺序        // 需要先放入map,否则有环时则会导致内存溢出        cacheNodeMap[node] = newNode        newNode.Next = deepCopy(node.Next)        newNode.Random = deepCopy(node.Random)        return newNode    }    return deepCopy(head)}
复制代码




欢迎关注公众号交流更多题目~


发布于: 刚刚阅读数: 4
用户头像

半亩房顶

关注

人生那么长,能写多少bug? 2018-11-16 加入

我希望,自己永远是自己。我希望,远离bug。

评论

发布
暂无评论
每日一题:LeetCode-138. 随机链表的复制_算法_半亩房顶_InfoQ写作社区