力扣每日一道系列 --- LeetCode 138. 随机链表的复制


在这里插入图片描述

📷 江池俊: 个人主页

🔥个人专栏: ✅数据结构探索 ✅LeetCode每日一道

🌅 有航道的人,再渺小也不会迷途。

LeetCode 138. 随机链表的复制

在这里插入图片描述

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

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

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

返回复制链表的头节点。

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

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

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

在这里插入图片描述

迭代 + 节点拆分

思路及算法:

此处的难点就是如何 copy 深拷贝的节点的 random ?
思路是:将 copy 的节点依次插入到相应节点的后面,从而保证 copy 与相应的节点保持联系,而要找 copy 的节点的 random
就是先找到与 copy 对应的节点的 random ,而 randomnext 就是 copy 节点的 random ,因为 copy 节点是对应节点的后一个节点,故 copy 节点的 random 就是对应节点的后一个,它们对应的位置是不变的,copy 节点总是对应节点的后一个位置这里可以理解为假设你目前是一个单身狗,你想要找一个女朋友,而你的好兄弟有女朋友这时,你通过你跟你好兄弟的这层关系就可以去找好兄弟的女朋友把他的闺蜜介绍给你。

  1. 我们首先将该链表中每一个节点拆分为两个相连的节点,例如对于链表 A→B→C,我们可以将其拆分为 A→A′→B→B′→C→C′
    对于任意一个原节点 S,其拷贝节点 S′ 即为其后继节点。
  2. 这样,我们可以直接找到每一个拷贝节点 S′ 的随机指针应当指向的节点,即为其原节点 S 的随机指针指向的节点 T 的后继节点
    T′。需要注意原节点的随机指针可能为空,我们需要特别判断这种情况。
  3. 当我们完成了拷贝节点的随机指针的赋值,我们只需要将这个链表按照原节点与拷贝节点的种类进行拆分即可,只需要遍历一次。同样需要注意最后一个拷贝节点的后继节点为空,我们需要特别判断这种情况。
    在这里插入图片描述 在这里插入图片描述
    在这里插入图片描述在这里插入图片描述
struct Node* copyRandomList(struct Node* head) {
    if(head==NULL)
    {
        return NULL;
    }
    //1.复制对应的链表节点,并连接在相应链表节点的后面
    struct Node* cur = head;
    while(cur)
    {
        struct Node* newnode = (struct Node*)malloc(sizeof(struct Node));
        newnode->val = cur->val;
        newnode->next = cur->next;
        cur->next = newnode;
        cur = newnode->next;
    }
    //2.处理复制链表节点的random
    cur = head;
    while(cur)
    {
        if(cur->random)
            cur->next->random = cur->random->next;
        else
            cur->next->random = NULL;
        cur = cur->next->next;
    }
    //3.将原链表和复制链表拆分开,返回复制链表的头节点
    struct Node* newhead = head->next;
    struct Node* newcur = newhead;
    head->next = head->next->next;
    cur = head->next;
    while(cur)
    {
        newcur->next = newcur->next->next;
        newcur = newcur->next;
        cur->next = cur->next->next;
        cur = cur->next;
    }
    newcur->next = NULL;
    return newhead;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/148080.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【双指针】:Leetcode283.移动零

朋友们、伙计们,我们又见面了,本专栏是关于各种算法的解析,如果看完之后对你有一定的启发,那么请留下你的三连,祝大家心想事成! C 语 言 专 栏:C语言:从入门到精通 数据结构专栏&…

[数据结构]—带头双向循环链表——超详解

💓作者简介🎉:在校大二迷茫大学生 💖个人主页🎉:小李很执着 💗系列专栏🎉:数据结构 每日分享✨:旅行是为了迷路,迷路是为了遇上美好❣️❣️❣️ …

Git的基本操作以及原理介绍

文章目录 基本操作创建git仓库配置name和email .git目录的结构git add & git commit.git目录结构的变化 git追踪管理的数据git的版本回退回退的原理回退的三种情况 版本库中文件的删除git分支管理分支的删除合并分支时的冲突分支的合并模式分支策略git stash不要在master分…

数据结构-时间复杂度与空间复杂度详解

文章目录 算法效率时间复杂度概念计算例1例2例3补充例4 空间复杂度例1例2 算法效率 算法效率分析分为两种:第一种是时间效率,第二种是空间效率。时间效率被称为时间复杂度,而空间效率被称作空间复杂度。时间复杂度主要衡量的是一个算法的运行速度&#…

Delicious Retouch5 for mac(PS磨皮插件DR5白金版)

Delicious Retouch5是一款强大的Photoshop插件,专为专业摄影师和摄影爱好者设计,提供一系列高级修图工具,帮助用户更快速、更有效地进行照片修饰和美化。其主要功能包括皮肤美容、人像润色、头发修饰、修复工具等,并配备定制化画笔…

海外邮件接收延迟、接收不到怎么办?U-Mail邮件网关来了

随着经济全球化的发展,很多国内企业开始踏足海外市场,电子邮件就成为了国内企业与海外客户沟通交流的主要渠道。然而海外邮件接收延迟、接收不到等问题成为了困扰企业与海外客户沟通的一大阻碍,导致客户邮件回复不及时,询盘邮件接…

新版本!飞凌嵌入式RK3568系列开发板全面支持Debian 11系统

飞凌嵌入式OK3568-C/OK3568J-C开发板现已全面支持Debian 11系统,新系统的加持能为用户提供主控新选择,并为开发者带来更多开发便利! Debian系统作为一种广受欢迎和信赖的开源操作系统,以其稳定性、可靠性和开放性而闻名&#xff0…

2013年5月23日 Go生态洞察:高级Go并发模式分析

🌷🍁 博主猫头虎(🐅🐾)带您 Go to New World✨🍁 🦄 博客首页——🐅🐾猫头虎的博客🎐 🐳 《面试题大全专栏》 🦕 文章图文…

OpenELA 正式公开 Enterprise Linux 源代码

导读近日消息,在红帽(Red Hat)宣布不再对外公开 Red Hat Enterprise Linux(RHEL)源代码之后,同属 Linux 领域的甲骨文、SUSE 及 CIQ 宣布成立了 Open Enterprise Linux Association(OpenELA&…

xstream实现xml和java bean 互相转换

目录 pom引用java bean 类XML 转换工具类测试类执行结果注意问题 Java中实现XML和Bean的转换的方式或插件有以下几种: JAXB(Java Architecture for XML Binding):JAXB是Java SE的一部分,可以将Java对象与XML文档相互转…

Linux 图形界面配置RAID

目录 RAID 1 配置 RAID 5配置 , RAID 配置起来要比 LVM 方便,因为它不像 LVM 那样分了物理卷、卷组和逻辑卷三层,而且每层都需要配置。我们在图形安装界面中配置 RAID 1和 RAID 5,先来看看 RAID 1 的配置方法。 RAID 1 配置 配置 RAID 1…

开源项目datavines内存泄漏问题分析

应用程序开启JMX java -Dspring.profiles.activemysql -Dcom.sun.management.jmxremote.port1099 -Dcom.sun.management.jmxremote.sslfalse -Dcom.sun.management.jmxremote.authenticatefalse -Djava.rmi.server.hostname127.0.0.1 -jar dataVines.jar 通过jdk自带工具&…

数据结构第四课 -----线性表之队列

作者前言 🎂 ✨✨✨✨✨✨🍧🍧🍧🍧🍧🍧🍧🎂 ​🎂 作者介绍: 🎂🎂 🎂 🎉🎉&#x1f389…

使用geek卸载windows软件,干净彻底

我们在电脑上安装软件,以及在使用软件的过程中,会产生一些程序文件、注册表项和临时文件等,用来支持软件的正常使用,都是正常现象。 但是,在卸载软件时,很多软件的卸载程序,并不能完全清除软件…

excel中正态分布函数NORM.DIST和NORMDIST,以及它们之间的区别

NORM.DIST和NORMDIST的区别 NORM.DIST和NORMDIST函数都可以返回正态分布的概率密度、或者正态累积分布。 根据微软官网上的说法,NORMDIST函数已经不建议使用了,它已经被一个或者几个新的函数代替(例如NORM.DIST),这些…

RabbitMQ-高级篇-黑马程序员

代码: 链接: https://pan.baidu.com/s/1nQBIgB_SbzoKu_XMWZ3JoA?pwdaeoe 提取码:aeoe 在昨天的练习作业中,我们改造了余额支付功能,在支付成功后利用RabbitMQ通知交易服务,更新业务订单状态为已支付。 但…

Python数据结构:集合(set)详解

1.集合的概念 在Python中,集合(Set)是一种无序、不重复的数据类型,它的实现基于哈希表,是由唯一元素组成的。集合中不允许有重复的元素,即相同元素只能出现一次。Python中的集合类似于数学中的集合&#xf…

你是想被ChatGPT改变,还是改变软件开发的未来?丨IDCF

人工智能技术的发展,正在深刻地改变着我们的生活和工作方式。在软件工程领域,ChatGPT作为一种新兴的人工智能技术,正在逐渐地被应用到软件开发的各个环节中。那么,ChatGPT对每个人的影响是什么呢? 一、对软件开发人员…

LockBit3.0的字符串解密方法

LockBit 与大多数勒索黑客团体一样以勒索软件即服务 (RaaS) 模式运行,该组织于 2019 年 9 月首次被观察到,此后发展为了今年最主要的勒索软件团伙,甚至超过了Conti、Hive等其他知名团体。据泄露数据站点的数据统计表明,LockBit占2022年第一季度所有与勒索软件相关的泄露事件…