剑指 Offer 35. 复杂链表的复制

这篇具有很好参考价值的文章主要介绍了剑指 Offer 35. 复杂链表的复制。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

请实现 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。

提示:

    -10000 <= Node.val <= 10000
    Node.random 为空(null)或指向链表中的节点。
    节点数目不超过 1000 。

 代码:文章来源地址https://www.toymoban.com/news/detail-617434.html

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(head == nullptr) return nullptr;
        Node* cur = head;
        unordered_map<Node*, Node*> map;
        // 3. 复制各节点,并建立 “原节点 -> 新节点” 的 Map 映射
        while(cur != nullptr) {
            map[cur] = new Node(cur->val);
            cur = cur->next;
        }
        cur = head;
        // 4. 构建新链表的 next 和 random 指向
        while(cur != nullptr) {
            map[cur]->next = map[cur->next];
            map[cur]->random = map[cur->random];
            cur = cur->next;
        }
        // 5. 返回新链表的头节点
        return map[head];
    }
};

到了这里,关于剑指 Offer 35. 复杂链表的复制的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • (链表) 剑指 Offer 52. 两个链表的第一个公共节点 ——【Leetcode每日一题】

    难度:简单 输入两个链表,找出它们的第一个公共节点。 如下面的两个链表: 在节点 c1 开始相交。 示例 1: 输入:intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3 输出:Reference of the node with value = 8 输入解释:相交节点的值为 8 (注意,如果两个列表相交则

    2024年02月15日
    浏览(51)
  • 【数据结构和算法初阶(C语言)】复杂链表(随机指针,随机链表的复制)题目详解+链表顺序表结尾

    目录  1.随机链表的复制 1.2题目描述  1.3题目分析 1.4解题: 2.顺序表和链表对比 2.1cpu高速缓存利用率 3.结语 一个长度为  n  的链表,每个节点包含一个额外增加的随机指针  random   该指针可以指向链表中的任何节点或空节点。        构造这个链表的  深拷贝 。 深拷贝

    2024年03月10日
    浏览(83)
  • 剑指offer刷题笔记-链表

    少年何妨梦摘星 敢挽桑弓射玉衡 解决与链表相关的问题总是有大量的指针操作,而指针操作的代码总是容易出错的。很多面试官喜欢出与链表相关的问题,就是想通过指针操作来考察应聘者的编码功底。 题目链接 来自于 AcWing 、 Leetcode (LCR) 目录  从尾到头打印链表 题目

    2024年02月21日
    浏览(35)
  • 剑指 Offer 24. 反转链表

    🚀 作者简介:一名在后端领域学习,并渴望能够学有所成的追梦人。 🚁 个人主页:不 良 🔥 系列专栏:🛸剑指 Offer  🛹Linux 📕 学习格言:博观而约取,厚积而薄发 🌹 欢迎进来的小伙伴,如果小伙伴们在学习的过程中,发现有需要纠正的地方,烦请指正,希望能够与诸

    2024年02月06日
    浏览(39)
  • 《剑指offer》——合并两个排序的链表

    本期给大家带来的是  合并两个排序的链表 这道题的讲解!!!  接下来,我们还是先从题干的内容入手,先分析一波题目,在进行画图思考操作。 💨  题目如下: 示例1 输入:{1,3,5},{2,4,6} 返回值:{1,2,3,4,5,6} 示例2 输入:{},{} 返回值:{} 示例3 输入:{-1,2,4},{1,3,4} 返回值:

    2023年04月13日
    浏览(34)
  • 剑指 Offer 06. 从尾到头打印链表

    🚀 作者简介:一名在后端领域学习,并渴望能够学有所成的追梦人。 🚁 个人主页:不 良 🔥 系列专栏:🛸剑指 Offer   📕 学习格言:博观而约取,厚积而薄发 🌹 欢迎进来的小伙伴,如果小伙伴们在学习的过程中,发现有需要纠正的地方,烦请指正,希望能够与诸君一同

    2024年02月08日
    浏览(42)
  • (链表) 剑指 Offer 24. 反转链表 ——【Leetcode每日一题】

    难度:简单 定义一个函数,输入一个链表的头节点,反转该链表并输出反转后链表的头节点。 示例: 输入 : 1-2-3-4-5-NULL 输出 : 5-4-3-2-1-NULL 限制 : 0 = 节点个数 = 5000 注意:本题与 206. 反转链表 相同。 💡思路: 法一:递归 可以将本问题分解成子问题: 1 - (剩余部分的反转)

    2024年02月15日
    浏览(47)
  • 剑指 Offer II 024. 反转链表(经典题型)

    时间是伟大的作者,她能写出未来的结局。                               ——卓别林 目录 题目描述: 方法1:迭代法(翻指针) 方法2:头插法  方法3:递归法  给定单链表的头节点 head ,请反转链表, 并返回反转后的链表的头节点 。 示例 1: 输入:head = [1,2,3,4,5]

    2023年04月09日
    浏览(35)
  • 剑指 offer 链表算法题:链表倒数第k个节点

    题目描述: 输入一个链表,输出该链表中倒数第k个节点。为了符合大多数人的习惯,本题从1开始计数,即链表的尾节点是倒数第1个节点。         例如,一个链表有 6 个节点,从头节点开始,它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点

    2024年02月13日
    浏览(34)
  • 剑指offer--JZ6 从尾到头打印链表

    我写不出来,参考别人的代码后理清思路后再写的C语言版本,代码如下: 最难理解的是创建结果数组那里。我竟然不知道有这种语法。我看了老半天。malloc动态申请的内存可以看作数组使用,而且能使用数组的方式来访问元素。 大致讲解下整体思路: 1.创建一个头结点hea

    2024年02月11日
    浏览(54)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包