数据结构——单链表OJ题(第二弹)

在这里插入图片描述

单链表OJ题

  • 前言
  • 一、返回链表开始入环的第一个节点
    • 思路一
    • 思路二
  • 二、返回链表的深度拷贝
  • 总结


前言

此次练习题有两道!
有点小难度,但相信难不住大家的!

我也会给出两道OJ题的链接,大家也赶快去试一试吧


一、返回链表开始入环的第一个节点

题目链接:OJ链接
在这里插入图片描述
在这里插入图片描述

提示:

链表中节点的数目范围在范围 [0, 104] 内
-105 <= Node.val <= 105
pos 的值为 -1 或者链表中的一个有效索引

本题有两个解析思路~
在这里插入图片描述
在这里插入图片描述

思路一

在这里插入图片描述
代码演示:

//解题方法一
struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode *move1=head;
    struct ListNode *move2=head;
    while(move1&&move2&&move2->next){//快慢指针移动
        move1=move1->next;
        move2=move2->next->next;
            if(move1==move2){{//找到相遇点
            struct ListNode *meet=move1;//meet从相遇点开始移动
            struct ListNode *move3=head;//move3从head开始移动
            while(meet!=move3){//两个指针同时移动找到起始点
                meet=meet->next;
                move3=move3->next;
            }
            return meet;
        }
    }
   
    return NULL;
}

思路二

在这里插入图片描述

提示:如果不了解如何找出公共点的的话,前面的博客会对大家有所帮助!
博客链接:单链表OJ题

代码演示:

//解题方法二
struct ListNode *detectCycle(struct ListNode *head) {
   struct ListNode *move1=head;
   struct ListNode *move2=head;
   while(move1&&move2&&move2->next){//快慢指针移动
        move1=move1->next;
        move2=move2->next->next;
        if(move1==move2){//找到相遇点
            struct ListNode *temp=move1;//保存相遇点位置
            move1=move1->next;//将move1变为第二链表起始点
            temp->next=NULL;//将相遇点的next置空
            struct ListNode *head1=head;
            struct ListNode *head2=move1;
            int len1=0,len2=0;
            while(head1!=NULL){//计算链表长度
                len1++;
                head1=head1->next;
            }
            while(head2!=NULL){
                head2=head2->next;
                len2++;
            }
            int k=abs(len1-len2);//得到两链表长度相减的绝对值
            //将longs指向较长的链表,shorts指向较短的链表
            struct ListNode *shorts=head;
            struct ListNode *longs=move1;
            if(len1>len2){
                shorts=move1;
                longs=head;
            }
            while(k--&&longs!=NULL){//较长的链表移动k位
                longs=longs->next;
            }
            if(k>0&&longs==NULL){
                return NULL;
            }
            while(shorts!=longs){//两链表同时遍历,找到第一个公共点
                shorts=shorts->next;
                longs=longs->next;
            }
            return longs;
         }
    }
    return NULL;
}

二、返回链表的深度拷贝

题目链接:OJ链接
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

提示:

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

解题思路:
在这里插入图片描述
在这里插入图片描述

代码演示

struct Node* BuyNewnode(int x){//创建结点函数
    struct Node*newnode=(struct Node*)malloc(sizeof(struct Node));
    newnode->val=x;
    newnode->next=NULL;
    newnode->random=NULL;
    return newnode;
}
//查找random所在位置的函数
struct Node* findrandom(struct Node* head,struct Node* newhead,struct Node* random){
    struct Node*move1=head;
    struct Node*move2=newhead;
    while(move1!=random){
        move1=move1->next;
        move2=move2->next;
    }
    return move2;
}

struct Node* copyRandomList(struct Node* head) {
	struct Node*move=head;
    struct Node*newhead=NULL;
    struct Node*tail=NULL;
    while(move!=NULL){//将新建结点依次尾插到新链表中
         if(tail==NULL){
            struct Node*newnode= BuyNewnode(move->val);
            newhead=tail=newnode;
            move=move->next;
         }
              else{
             struct Node*newnode= BuyNewnode(move->val);
             tail->next=newnode;
             tail=tail->next;
             move=move->next;
         }
    }
    struct Node*setran=newhead;
    struct Node*findran=head;
      while(setran&&findran){
        struct Node*temp=findrandom(head,newhead,findran->random);
        setran->random=temp;
        setran=setran->next;
        findran=findran->next;
    }
    return newhead;
}

总结

这次的题目稍稍有些难度!
但是绝对难不倒大家的!
加油! 加油!

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

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

相关文章

浅聊Cesium.js 后处理原理

浅聊Cesium.js 后处理原理 使用例子: const stages viewer.scene.postProcessStages;const silhouette Cesium.PostProcessStageLibrary.createSilhouetteStage() silhouette.enabled true; stages.add(silhouette);silhouette.uniforms.color Cesium.Color.LIME;涉及到相…

OSPF作业3

题目 地址配置 R1&#xff1a; R2&#xff1a; R3&#xff1a; R4&#xff1a; R5&#xff1a; R6&#xff1a; R7&#xff1a; R8&#xff1a; R9&#xff1a; R10&#xff1a; R11&#xff1a; R12&#xff1a; 私网通及LSDB优化 R1&#xff1a; ospf 1 router-id 1.1.1.1 …

关于Godot游戏引擎制作流水灯

先上核心代码 游戏节点 流水灯的通途可以是 1. 装饰 2. 音乐类多媒体程序&#xff08;如FL中TB-303的步进灯&#xff09; FL Studio Transistor Bass

STM32基础入门学习笔记:内部高级功能应用

文章目录&#xff1a; 一&#xff1a;低功耗模式 1.睡眠模式测试程序 NVIC.h NVIC.c key.h key.c main.c 2.停机模式测试程序 main.c 3.待机模式测试程序 main.c 二&#xff1a;看门狗 1.独立看门狗测试程序 iwdg.h iwdg.c main.c 2.窗口看门狗测试程序 wwdg…

深入理解缓存 TLB 原理

今天分享一篇TLB的好文章&#xff0c;希望大家夯实基本功&#xff0c;让我们一起深入理解计算机系统。 TLB 是 translation lookaside buffer 的简称。首先&#xff0c;我们知道 MMU 的作用是把虚拟地址转换成物理地址。 MMU工作原理 虚拟地址和物理地址的映射关系存储在页表…

Go语音介绍

Go语言介绍 Go 即Golang&#xff0c;是Google公司2009年11月正式对外公开的一门编程语言。 Go是静态强类型语言&#xff0c;是区别于解析型语言的编译型语言。 解析型语言——源代码是先翻译为中间代码&#xff0c;然后由解析器对代码进行解释执行。 编译型语言——源代码编…

20230807通过ffmpeg将DTS编码的AUDIO音频转换为AAC编码

20230807通过ffmpeg将DTS编码的AUDIO音频转换为AAC编码 2023/8/7 20:04 ffmpeg dts 转AAC 缘起&#xff1a;由于网上找的电影没有中文字幕&#xff0c;有内置的英文字幕&#xff0c;但是还是通过剪映/RP2023识别一份英文字幕备用&#xff01; I:\Downloads\2005[红眼航班]Red E…

【C++】Lambda表达式的使用

学习目标&#xff1a; 例如&#xff1a; 了解Lambda的优点 掌握Lambda表达式的使用 了解Lambda表达式的底层原理 学习内容&#xff1a; Lambda表达式的语法 文章目录 学习目标&#xff1a;学习内容&#xff1a;Lambda表达式排序案例Lambda表达式语法捕捉列表Lambda表达式模拟…

【Java设计模式】建造者模式 注解@Builder

概念 将一个复杂对象的构造与它的表示分离&#xff0c;使同样的构建过程可以创建不同的表示。它使将一个复杂的对象分解成多个简单的对象&#xff0c;然后一步步构建而成。 每一个具体建造者都相对独立&#xff0c;而与其它的具体建造者无关&#xff0c;因此可以很方便地替换具…

深度学习论文: RepViT: Revisiting Mobile CNN From ViT Perspective及其PyTorch实现

深度学习论文: RepViT: Revisiting Mobile CNN From ViT Perspective及其PyTorch实现 RepViT: Revisiting Mobile CNN From ViT Perspective PDF: https://arxiv.org/pdf/2307.09283.pdf PyTorch代码: https://github.com/shanglianlm0525/CvPytorch PyTorch代码: https://gith…

【并发专题】单例模式的线程安全(进阶理解篇)

目录 背景前置知识类加载运行全过程 单例模式的实现方式一、饿汉式基本介绍源码分析 二、懒汉式基本介绍源码分析改进 三、懒汉式单例终极解决方案&#xff08;静态内部类&#xff09;&#xff08;推荐使用方案&#xff09;基本介绍源码分析 感谢 背景 最近学习了JVM之后&…

Permute 3 for mac音视频格式转换

Permute是一款Mac平台上的媒体格式转换软件&#xff0c;由Chaotic Software开发。它可以帮助用户快速地将各种音频、视频和图像文件转换成所需格式&#xff0c;并提供了一些常用工具以便于用户进行编辑和处理。 Permute的主要特点包括&#xff1a; - 支持大量格式&#xff1a;支…

2020年09月 Python(一级)真题解析#中国电子学会#全国青少年软件编程等级考试

一、单选题 第1题 Python自带的编程环境是&#xff1f; A&#xff1a;PyScripter B&#xff1a;Spyder C&#xff1a;Notepad D&#xff1a;IDLE 正确的答案是&#xff1a;D Python自带的编程环境是IDLE&#xff08;Integrated Development and Learning Environment&a…

【c语言初级】c++基础

文章目录 1. C关键字2. 命名空间2.1 命名空间定义2.2 命名空间使用 3. C输入&输出4. 缺省参数4.1 缺省参数概念4.2 缺省参数分类 5. 函数重载5.2 C函数重载的原理--名字修饰采用C语言编译器编译后结果 1. C关键字 C是在C的基础之上&#xff0c;容纳进去了面向对象编程思想…

【分布式能源选址与定容】光伏、储能双层优化配置接入配电网研究(Matlab代码实现)

目录 &#x1f4a5;1 概述 &#x1f4da;2 运行结果 &#x1f389;3 参考文献 &#x1f308;4 Matlab代码、数据、讲解 &#x1f4a5;1 概述 由于能源的日益匮乏&#xff0c;电力需求的不断增长等&#xff0c;配电网中分布式能源渗透率不断提高&#xff0c;且逐渐向主动配电网方…

Android平台一对一音视频通话方案对比:WebRTC VS RTMP VS RTSP

一对一音视频通话使用场景 一对一音视频通话都需要稳定、清晰和流畅&#xff0c;以确保良好的用户体验&#xff0c;常用的使用场景如下&#xff1a; 社交应用&#xff1a;社交应用是一种常见的使用场景&#xff0c;用户可以通过音视频通话进行面对面的交流&#xff1b;在线教…

OLAP ModelKit Crack,ADO.NET和IList

OLAP ModelKit Crack,ADO.NET和IList OLAP ModelKit是一个多功能的.NET OLAP组件&#xff0c;用C#编写&#xff0c;只包含100%托管代码。它具有XP主题的外观&#xff0c;并能够使用任何.NET数据源(ADO.NET和IList)。借助任何第三方组件(尤其是图表组件)呈现数据的能力扩展了产品…

Pytorch深度学习-----损失函数(L1Loss、MSELoss、CrossEntropyLoss)

系列文章目录 PyTorch深度学习——Anaconda和PyTorch安装 Pytorch深度学习-----数据模块Dataset类 Pytorch深度学习------TensorBoard的使用 Pytorch深度学习------Torchvision中Transforms的使用&#xff08;ToTensor&#xff0c;Normalize&#xff0c;Resize &#xff0c;Co…

【Hystrix技术指南】(5)Command创建和执行实现

创建流程 构建HystrixCommand或者HystrixObservableCommand对象 *使用Hystrix的第一步是创建一个HystrixCommand或者HystrixObservableCommand对象来表示你需要发给依赖服务的请求。 若只期望依赖服务每次返回单一的回应&#xff0c;按如下方式构造一个HystrixCommand即可&a…

24届近5年江南大学自动化考研院校分析

今天给大家带来的是江南大学控制考研分析 满满干货&#xff5e;还不快快点赞收藏 一、江南大学 学校简介 江南大学&#xff08;Jiangnan University&#xff09;是国家“双一流”建设高校&#xff0c;“211工程”、“985工程优势学科创新平台”重点建设高校&#xff0c;入选…
最新文章