【LeetCode刷题日志】138.随机链表的复制

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

【LeetCode刷题日志】138.随机链表的复制,LeetCode 刷题日志,leetcode,链表,算法,职场和发展,linux

  • 🎈个人主页:库库的里昂
  •  🎐C/C++领域新星创作者
  •  🎉欢迎 👍点赞✍评论⭐收藏
  • ✨收录专栏:LeetCode 刷题日志
  • 🤝希望作者的文章能对你有所帮助,有不足的地方请在评论区留言指正,大家一起学习交流!🤗

目录

1.题目描述

2.解题思路+代码实现

方法:迭代 + 节点拆分

思路及算法:

代码实现:


1.题目描述

OJ链接 【leetcode 题号:138.随机链表的复制】【难度:中等】

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

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

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

返回复制链表的头节点。

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

  • val:一个表示 Node.val 的整数。
  • random_index:随机指针指向的节点索引(范围从 0 到 n-1);如果不指向任何节点,则为  null 。

你的代码  接受原链表的头节点 head 作为传入参数。

示例 1:

【LeetCode刷题日志】138.随机链表的复制,LeetCode 刷题日志,leetcode,链表,算法,职场和发展,linux

输入:head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出:[[7,null],[13,0],[11,4],[10,2],[1,0]]

示例 2:

【LeetCode刷题日志】138.随机链表的复制,LeetCode 刷题日志,leetcode,链表,算法,职场和发展,linux

输入:head = [[1,1],[2,1]]
输出:[[1,1],[2,1]]

示例 3:

【LeetCode刷题日志】138.随机链表的复制,LeetCode 刷题日志,leetcode,链表,算法,职场和发展,linux

输入:head = [[3,null],[3,0],[3,null]]
输出:[[3,null],[3,0],[3,null]]

提示:

  • 0 <= n <= 1000
  • -104 <= Node.val <= 104
  • Node.random 为 null 或指向链表中的节点。

2.解题思路+代码实现

方法:迭代 + 节点拆分
思路及算法:

注意到方法一需要使用哈希表记录每一个节点对应新节点的创建情况,而我们可以使用一个小技巧来省去哈希表的空间。

我们首先将该链表中每一个节点拆分为两个相连的节点,例如对于链表A→B→C,我们可以将其拆分为 A→A′→B→B′→C→C′。对于任意一个原节点S,其拷贝节点S′即为其后继节点。

这样,我们可以直接找到每一个拷贝节点S′的随机指针应当指向的节点,即为其原节点S的随机指针指向的节点T的后继节点T′。需要注意原节点的随机指针可能为空,我们需要特别判断这种情况。

当我们完成了拷贝节点的随机指针的赋值,我们只需要将这个链表按照原节点与拷贝节点的种类进行拆分即可,只需要遍历一次。同样需要注意最后一个拷贝节点的后继节点为空,我们需要特别判断这种情况。

【LeetCode刷题日志】138.随机链表的复制,LeetCode 刷题日志,leetcode,链表,算法,职场和发展,linux

【LeetCode刷题日志】138.随机链表的复制,LeetCode 刷题日志,leetcode,链表,算法,职场和发展,linux

【LeetCode刷题日志】138.随机链表的复制,LeetCode 刷题日志,leetcode,链表,算法,职场和发展,linux

【LeetCode刷题日志】138.随机链表的复制,LeetCode 刷题日志,leetcode,链表,算法,职场和发展,linux

代码实现:
struct Node* copyRandomList(struct Node* head) {
    if (head == NULL) {
        return NULL;
    }
    for (struct Node* node = head; node != NULL; node = node->next->next) {
        struct Node* nodeNew = malloc(sizeof(struct Node));
        nodeNew->val = node->val;
        nodeNew->next = node->next;
        node->next = nodeNew;
    }
    for (struct Node* node = head; node != NULL; node = node->next->next) {
        struct Node* nodeNew = node->next;
        nodeNew->random = (node->random != NULL) ? node->random->next : NULL;
    }
    struct Node* headNew = head->next;
    for (struct Node* node = head; node != NULL; node = node->next) {
        struct Node* nodeNew = node->next;
        node->next = node->next->next;
        nodeNew->next = (nodeNew->next != NULL) ? nodeNew->next->next : NULL;
    }
    return headNew;
}

复杂度分析

  • 时间复杂度:O(n),其中 nnn 是链表的长度。我们只需要遍历该链表三次。
  • 空间复杂度:O(1)。注意返回值不计入空间复杂度。

读者们也可以自行尝试在计算拷贝节点的随机指针的同时计算其后继指针,这样只需要遍历两次。

【LeetCode刷题日志】138.随机链表的复制,LeetCode 刷题日志,leetcode,链表,算法,职场和发展,linux文章来源地址https://www.toymoban.com/news/detail-755931.html

到了这里,关于【LeetCode刷题日志】138.随机链表的复制的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 【LeetCode-中等题】138. 复制带随机指针的链表

    这里的拷贝属于深拷贝,就是不光是拷贝值,还要拷贝其指针的引用情况。如果只是单独的单向链表,则直接可以根据next指向找到下一个结点,然后创建一个新节点复制过来,直接拷贝,但是题目中的random指针指向的节点是没有归类的,这样我们就不可能使用普通的循环来进

    2024年02月10日
    浏览(50)
  • leetcode做题笔记138. 复制带随机指针的链表

    给你一个长度为 n 的链表,每个节点包含一个额外增加的随机指针 random ,该指针可以指向链表中的任何节点或空节点。 构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成,其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 

    2024年02月07日
    浏览(39)
  • 【数据结构】[LeetCode138. 复制带随机指针的链表]

    给你一个长度为  n  的链表,每个节点包含一个额外增加的随机指针  random  ,该指针可以指向链表中的任何节点或空节点。 构造这个链表的  深拷贝 。 深拷贝应该正好由  n  个  全新  节点组成,其中每个新节点的值都设为其对应的原节点的值。新节点的  next  指针和

    2024年02月04日
    浏览(48)
  • Leetcode刷题之复制带随机指针的链表

    生命不是安排,而是追求,人生的意义也许永远没有答案,但也要尽情感受这种没有答案的人生。                                                                                                                     --弗吉尼亚.  伍尔芙         目录 前言:

    2024年02月04日
    浏览(44)
  • 反转链表、链表的中间结点、合并两个有序链表【LeetCode刷题日志】

    给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。 力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 这里解释一下三个指针的作用: n1:记录上一个节点,如果是第一个就指向空 n2:记录此节点的位置 n3:记录下一个节点的位置,让翻转后能找到下一个节点

    2024年02月03日
    浏览(49)
  • 单链表OJ题:LeetCode--138.复制带随即指针的链表

    朋友们、伙计们,我们又见面了,本期来给大家解读一下LeetCode中第138道单链表OJ题,如果看完之后对你有一定的启发,那么请留下你的三连,祝大家心想事成! 数据结构与算法专栏 : 数据结构与算法 个  人  主  页  : stackY、 C 语 言 专 栏 : C语言:从入门到精通  Lee

    2024年02月08日
    浏览(66)
  • 【LeetCode】 复制带随机指针的链表

    Leetcode 138.复制带随机指针的链表 给你一个长度为 n 的链表,每个节点包含一个额外增加的随机指针 random ,该指针可以指向链表中的任何节点或空节点。 构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成,其中每个新节点的值都设为其对应的原节点的值。新节

    2024年02月08日
    浏览(47)
  • 【Leetcode刷题】链表的中间结点和合并两个有序链表

    生命如同寓言,其价值不在与长短,而在与内容。                                ——塞涅卡 目录 一.链表的中间结点 1.快慢指针 二.合并两个有序链表  1.尾插法 给你单链表的头结点 head ,请你找出并返回链表的中间结点。 如果有两个中间结点,则返回第二个中间结点

    2023年04月17日
    浏览(42)
  • 138. 复制带随机指针的链表

    给你一个长度为 n 的链表,每个节点包含一个额外增加的随机指针 random ,该指针可以指向链表中的任何节点或空节点。 构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成,其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应

    2024年02月13日
    浏览(64)
  • 【LeetCode】数据结构题解(9)[复制带随机指针的链表]

    所属专栏:玩转数据结构题型❤️ 🚀 博主首页:初阳785❤️ 🚀 代码托管:chuyang785❤️ 🚀 感谢大家的支持,您的点赞和关注是对我最大的支持!!!❤️ 🚀 博主也会更加的努力,创作出更优质的博文!!❤️ 🚀 关注我,关注我,关注我,重要的事情说三遍!!!!!

    2024年02月11日
    浏览(57)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包