LeetCode 138.复制带随机指针的链表

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

LeetCode 138.复制带随机指针的链表,C/C++刷题系列,leetcode,链表,算法,数据结构,c语言


LeetCode 138.复制带随机指针的链表,C/C++刷题系列,leetcode,链表,算法,数据结构,c语言
题目链接👉 LeetCode 138.复制带随机指针的链表👈

💡题目分析

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

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

LeetCode 138.复制带随机指针的链表,C/C++刷题系列,leetcode,链表,算法,数据结构,c语言
LeetCode 138.复制带随机指针的链表,C/C++刷题系列,leetcode,链表,算法,数据结构,c语言
LeetCode 138.复制带随机指针的链表,C/C++刷题系列,leetcode,链表,算法,数据结构,c语言
LeetCode 138.复制带随机指针的链表,C/C++刷题系列,leetcode,链表,算法,数据结构,c语言
LeetCode 138.复制带随机指针的链表,C/C++刷题系列,leetcode,链表,算法,数据结构,c语言

💡解题思路

🚩步骤一:拷贝节点插入到原节点的后面

🍄初始情况:
LeetCode 138.复制带随机指针的链表,C/C++刷题系列,leetcode,链表,算法,数据结构,c语言

①先将链表拷贝一层,让头指针cur的next指向一个新创建的拷贝节点,并将拷贝节点的next指向cur没发生变化之前的next。即在每个节点的后面再插入一个与他相同的节点。
LeetCode 138.复制带随机指针的链表,C/C++刷题系列,leetcode,链表,算法,数据结构,c语言
cur一直向后走,一直重复①步骤即可得到拷贝节点(图中米黄色线条)
LeetCode 138.复制带随机指针的链表,C/C++刷题系列,leetcode,链表,算法,数据结构,c语言

🍩步骤一代码

	//1、拷贝节点插入在原节点的后面
    struct Node* cur = head;
    while(cur)
    {
        struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
        copy->val = cur->val;

        struct Node* next = cur->next;
        //插入
        cur->next = copy;
        copy->next = next;

        cur = next;
    }

🚩步骤二:控制拷贝节点的random进行连接

②再将拷贝链表的random进行连接,由于原链表中每个节点的next都是拷贝链表中的节点,因此再将原链表中节点的random给拷贝链表的过程中,只需给random的next即可(copy->random = cur->random->next;)(图中紫色线条)
LeetCode 138.复制带随机指针的链表,C/C++刷题系列,leetcode,链表,算法,数据结构,c语言

🍩步骤二代码

	//2、控制拷贝节点的random
    cur = head;
    while(cur)
    {
        struct Node* copy = cur->next;

        if(cur->random == NULL)
        {
            copy->random = NULL;
        }
        else
        {
            copy->random = cur->random->next;
        }

        cur = copy->next;
    }

🚩步骤三:拷贝节点解下来尾插 组成拷贝链表,恢复原链表

③将拷贝出来的链表与原链表进行断开,即将拷贝节点的next指向原节点的next->next->next,即可完成断开。使拷贝链表的节点依次进行尾插,然后恢复原链表,返回拷贝节点的头即可(图中橙色线条)
LeetCode 138.复制带随机指针的链表,C/C++刷题系列,leetcode,链表,算法,数据结构,c语言

🍩步骤三代码

	//3、拷贝节点解下来尾插组成拷贝链表,恢复原链表
    struct Node* copyHead = NULL;
    struct Node* copyTail = NULL;

    cur = head;
    while(cur)
    {
        struct Node* copy = cur->next;
        struct Node* next = copy->next;

        //尾插
        if(copyTail == NULL)
        {
            copyHead = copyTail = copy;
        }
        else
        {
            copyTail->next = copy;
            copyTail = copyTail->next;
        }

        //恢复原链表
        cur->next = next;

        cur = next;
    }

🔔接口源码

struct Node* copyRandomList(struct Node* head) 
{
	//1、拷贝节点插入在原节点的后面
    struct Node* cur = head;
    while(cur)
    {
        struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
        copy->val = cur->val;

        struct Node* next = cur->next;
        //插入
        cur->next = copy;
        copy->next = next;

        cur = next;
    }

    //2、控制拷贝节点的random
    cur = head;
    while(cur)
    {
        struct Node* copy = cur->next;

        if(cur->random == NULL)
        {
            copy->random = NULL;
        }
        else
        {
            copy->random = cur->random->next;
        }

        cur = copy->next;
    }

    //3、拷贝节点解下来尾插组成拷贝链表,恢复原链表
    struct Node* copyHead = NULL;
    struct Node* copyTail = NULL;

    cur = head;
    while(cur)
    {
        struct Node* copy = cur->next;
        struct Node* next = copy->next;

        //尾插
        if(copyTail == NULL)
        {
            copyHead = copyTail = copy;
        }
        else
        {
            copyTail->next = copy;
            copyTail = copyTail->next;
        }

        //恢复原链表
        cur->next = next;

        cur = next;
    }

    return copyHead;
}

LeetCode 138.复制带随机指针的链表,C/C++刷题系列,leetcode,链表,算法,数据结构,c语言

🥰本道题目有一定的难度,希望烙铁们能够消化理解欧!

总结🥰
以上就是本题讲解的全部内容啦🥳🥳🥳🥳
本文章所在【C/C++刷题系列】专栏,感兴趣的烙铁可以订阅本专栏哦🥳🥳🥳
前途很远,也很暗,但是不要怕,不怕的人面前才有路。💕💕💕
小的会继续学习,继续努力带来更好的作品😊😊😊
创作写文不易,还多请各位大佬uu们多多支持哦🥰🥰🥰

LeetCode 138.复制带随机指针的链表,C/C++刷题系列,leetcode,链表,算法,数据结构,c语言文章来源地址https://www.toymoban.com/news/detail-673434.html

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

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

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

相关文章

  • 138. 复制带随机指针的链表

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

    2024年02月13日
    浏览(65)
  • 138. 复制带随机指针的链表(深拷贝)题解

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

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

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

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

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

    2024年02月08日
    浏览(48)
  • 【LeetCode刷题日志】138.随机链表的复制

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

    2024年02月04日
    浏览(39)
  • 【刷题专栏—突破思维】LeetCode 138. 随机链表的复制

    前言 随机链表的复制涉及到复制一个链表,该链表不仅包含普通的next指针,还包含random指针,该指针指向链表中的任意节点或空节点。 题目链接: LeetCode 138. 随机链表的复制 题目介绍: 给你一个长度为 n 的链表,每个节点包含一个额外增加的随机指针 random ,该指针可以指

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

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

    2024年02月11日
    浏览(59)
  • 【数据结构】LeetCode升级版的环形链表,复制带随机指针的链表

              1、题目说明           2、题目解析           1、题目说明           2、题目解析      1、题目说明 题目链接: 升级版的环形链表  给定一个链表的头节点 head ,返回链表开始入环的第一个节点。  如果链表无环,则返回NULL。 如果链表中有某个节点,可以通

    2024年01月16日
    浏览(62)
  • 力扣每日一道系列 --- LeetCode 138. 随机链表的复制

    📷 江池俊: 个人主页 🔥个人专栏: ✅数据结构探索 ✅LeetCode每日一道 🌅 有航道的人,再渺小也不会迷途。 LeetCode 138. 随机链表的复制 给你一个长度为 n 的链表,每个节点包含一个额外增加的随机指针 random ,该指针可以指向链表中的任何节点或空节点。 构造这个链表的

    2024年02月04日
    浏览(47)
  • 力扣-复制带随机指针的链表

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

    2024年02月11日
    浏览(47)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包