【数据结构练习】单链表OJ题(二)

目录

    • 一、相交链表
    • 二、环形链表1
    • 三、环形链表2
    • 四、链表分割
    • 五、复制带随机指针的链表

一、相交链表

题目:
在这里插入图片描述
示例:
在这里插入图片描述
注意:不能根据节点的值来比较是否相交,而是根据节点在内存中是否指向相同的位置。

例如以上图:

链表A:4、1、8、4、5
链表B:5、6、1、8、4、5

链表A和链表B都有节点的值为1,但是它们在内存中指向不同的位置,而值为8的节点(A的第三个节点、B的第四个节点)则在内存中指向相同的位置。

大体思路:链表A和链表B如果相交,那么它们的后几个或者一个节点的位置是一样的。它们的长度不一定一样长,所以要先计算出链表A和链表B的长度,让较长的链表先走长度差的距离,然后再同时走,直到两个链表相交,返回那个开始相交的节点。

计算链表长度:
分别定义一个变量遍历链表,不为空计数器加1往后走,直到循环结束跳出。

如果没有相交返回空:
此时分别遍历两个链表的指针已经走到尾了。假设两个链表有相交,不管是一个还是多个,那么这两个指针肯定是一样的(指相交);如果两个链表不相交,即使是最后的节点也同样不相交,所以就直接返回NULL。

较长的链表先走节点数之差:
用一个变量等于链表长度之差,因为并不知道是A链表长还是B链表长,所以使用绝对值函数abs。先假设是A链表长,B链表短。设置一个条件,如果A链表的长度小于B链表的长度,就反过来。如果假设的是对的,较长的链表先走长度之差的距离。

一起走,直到相交:
两个链表同时走到某个节点相交了,就跳出循环,然后赋给新的头指针,并且返回这个头指针。

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {int len1=0;int len2=0;struct ListNode *cur1=headA;struct ListNode *cur2=headB;//先算出两个链表的节点数while(cur1){len1++;cur1=cur1->next;}while(cur2){len2++;cur2=cur2->next;}//如果没有相加点返回空if(cur1!=cur2){return NULL;}//长的先走节点数之差int k=abs(len1-len2);struct ListNode *longhead=headA;struct ListNode *shorthead=headB;if(len1<len2){longhead=headB;shorthead=headA;}while(k){longhead=longhead->next;k--;}//一起走,直到相交while(longhead!=shorthead){longhead=longhead->next;shorthead=shorthead->next;}struct ListNode *newhead=longhead;return newhead;
}

二、环形链表1

题目:
在这里插入图片描述
使用的是双指针法

定义两个快慢指针fast和slow,从起点出发。先fast一次走两步,slow一次走一步,再判断两个指针是否相同。如果链表有环,那么fast或者fast->next永远不为空,一直在循环里转;如果链表没有环,fast又走得比slow快,所以fast或者fast->next到空就结束。这里fast比slow快一步,即每次距离缩短1步,所以只要有环,fast先在环里转,然后slow随后进环,每次它们的距离缩短1,最终相遇。

bool hasCycle(struct ListNode *head) {struct ListNode *slow=head;struct ListNode *fast=head;while(fast&&fast->next){slow=slow->next;fast=fast->next->next;if(slow==fast){return true;}}return false;
}

三、环形链表2

题目:
在这里插入图片描述
这题与上面的题多增加了一个设定,如果有环,返回的是开始入环的第一个节点。没有环返回空。

那么始入环的第一个节点怎么找呢?其实这里是有关数学计算的。

还是使用两个快慢指针,fast一次走两步,slow一次走一步。如果链表没有环,fast或者fast->next为空,然后返回空指针。如果链表有环,在环的某个位置相遇(注意:fast先入环,可能已经在环里转了n圈了)。假设相遇点与入环点的距离为x,起始点到入环点的距离为L,环的剩下的距离为nC-x(n表示fast已经在环里转了n圈)。

fast从起始点到相遇点的距离为:L+nC+x
slow从起始点到相遇点的距离为:L+x

因为fast一次的步长为slow的两倍

所以:
2(L+x)=L+nC+x
L+x=nC
L=nC-x

根据数学计算转换为:两个指针分别一个从相遇点走,另一个从起始点走,以相同的步长,它们会在入环的第一个节点相遇,然后返回这个相遇点就是入环的第一个节点。

在这里插入图片描述

struct ListNode *detectCycle(struct ListNode *head) {struct ListNode *slow=head;struct ListNode *fast=head;while(fast&&fast->next){fast=fast->next->next;slow=slow->next;if(slow==fast){struct ListNode *rid=slow;struct ListNode *mrid=head;while(rid!=mrid){rid=rid->next;mrid=mrid->next;}return rid;}}return NULL;
}

四、链表分割

题目:
在这里插入图片描述
假设一个链表为:

2、3、1、4、2、5

假设x等于3,数据小于的3的节点有:2、1、2
大于等于3的节点有:3、4、5

题目要求将小于x的节点排在其余节点之前,并且不能改变原来的数据顺序。

大体思路:这里我们可以采用分为两个链表的方式。将数据小于x的节点放在一个A链表里,大于等于的放在B链表里。然后把A链表的尾节点与B链表的头节点连接起来。

但是这里要注意一个问题,如果A链表没有节点怎么与B链表连接,这种情况要单独判断,比较麻烦。所以我们可以采用创建哨兵位头节点解决这个问题。

注意:最后B链表的尾节点要指向空指针,同时释放两个哨兵位节点,返回第一个有效节点。
在这里插入图片描述

class Partition {
public:ListNode* partition(ListNode* pHead, int x) {struct ListNode* cur=pHead;struct ListNode* head1, *tail1, *head2, *tail2;head1=tail1=(struct ListNode*)malloc(sizeof(struct ListNode));head2=tail2=(struct ListNode*)malloc(sizeof(struct ListNode));while(cur){if(cur->val<x){tail1->next=cur;tail1=tail1->next;}else{tail2->next=cur;tail2=tail2->next;}cur=cur->next;}tail2->next=NULL;tail1->next=head2->next;struct ListNode* newhead=head1->next;free(head1);free(head2);return newhead;}
};

五、复制带随机指针的链表

题目:
在这里插入图片描述
要拷贝原节点,并且拷贝节点的随机指针也要指向对应的节点,最后还原原链表。

每个拷贝节点都在原节点的后面:
用一个变量cur遍历链表,只要不为空每次进入循环先定义一个变量next记录原链表的下一个位置(cur在原链表的下一个位置,方便一次拷贝完找到),然后开辟一块空间copy为拷贝节点,把原节点的值赋给拷贝节点,再让cur的下一个地址为copy,copy连接next。
在这里插入图片描述
置每个拷贝random:
原链表的每个节点的random指针都有对应的指向,拷贝节点也要有random指针对应的指向,只是拷贝节点的random指针要与原节点的random指针指向保持一致。比如原节点13的random指针指向原节点的7,那么拷贝节点13的random指针则指向拷贝节点的7。

问题是拷贝节点的random指针怎么找到它对应的节点呢?其实上面一步把每个拷贝节点放在原节点的后面有一个好处,方便这一步找到它的random指针。

以拷贝节点13为例:拷贝节点13的random指针,就是它的原节点的random指针所指向的原节点的下一个节点。如果原节点的random指向空,拷贝节点的randon也是指向空。

在这里插入图片描述
拷贝节点解下来,尾插在一起,恢复原链表:
在这里插入图片描述

struct Node* copyRandomList(struct Node* head) {struct Node* cur=head;//复制某个节点到原节点的后面while(cur){struct Node* next=cur->next;struct Node* copy=(struct Node*)malloc(sizeof(struct Node));copy->val=cur->val;cur->next=copy;copy->next=next;cur=next;}cur=head;//处理拷贝节点的random指针指向while(cur){struct Node* copy=cur->next;if(cur->random==NULL){copy->random=NULL;}else{copy->random=cur->random->next;}cur=copy->next;}cur=head;//把拷贝指针连接起来,还原原来的链表struct Node* newhead=NULL;struct Node* tail=NULL;while(cur){struct Node* copy=cur->next;struct Node* next=copy->next;if(tail==NULL){newhead=tail=copy;}else{tail->next=copy;tail=tail->next;}cur->next=next;cur=next;}return newhead;
}

在这里插入图片描述
感谢观看~

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

深入解析:如何打造高效的直播视频美颜SDK

在当今数字化时代&#xff0c;视频直播已经成为人们交流、娱乐和信息传递的重要方式。然而&#xff0c;许多人在直播时都希望能够呈现出最佳的外观&#xff0c;这就需要高效的直播视频美颜技术。本文将深入解析如何打造高效的直播视频美颜SDK&#xff0c;以实现令人满意的视觉效…

Embedding 向量生成GPT数据使用相关

如果使用python3.6的版本&#xff0c;使用pycharm创建工程&#xff0c;那么默认会使用 docx包&#xff0c;这样运行程序会爆异常&#xff0c;突然想起以前请教的一个大神&#xff0c;想当 初&#xff0c;这个问题困扰了我 两天时间&#xff0c;在此记录一下&#xff1a; pytho…

skywalking服务部署

一、前言 Apache SkyWalking 是一个开源的分布式跟踪、监控和诊断系统&#xff0c;旨在帮助用户监控和诊断分布式应用程序、微服务架构和云原生应用的性能和健康状况。它提供了可视化的分析工具&#xff0c;帮助开发人员和运维团队深入了解应用程序的性能、调用链和异常情况 …

信创国产系统麒麟arm架构中nginx安装过程

前言 在事业单位或国企&#xff0c;信创项目在步步推进&#xff0c;下面将在国产系统通信arm架构中nginx的安装过程记录分享出来&#xff0c;希望帮助到有需要的小伙伴。 1、nginx下载 1.1、在线下载 进入指定目录&#xff0c;如/usr/local&#xff0c;执行如下命令&#x…

[C++] STL_vector使用与常用接口的模拟实现

文章目录 1、vector的介绍2、vector的使用2.1 vector的定义2.2 vector迭代器的使用2.3 vector的空间增长问题 3、vector的增删查改3.1 push_back&#xff08;重点&#xff09;3.2 pop_back&#xff08;重点&#xff09;3.3 operator[]&#xff08;重点&#xff09;3.4 insert3.…

【Android】Mobile-Security-Framework-MobSF Manifest 静态扫描规则

前言 移动安全框架&#xff08;MobSF&#xff09;是一个自动化的一体化移动应用程序&#xff08;Android/iOS/Windows&#xff09;测试、恶意软件分析和安全评估框架&#xff0c;能够执行静态和动态分析。MobSF支持移动应用程序二进制文件&#xff08;APK、XAPK、IPA和APPX&am…

深度学习论文: WinCLIP: Zero-/Few-Shot Anomaly Classification and Segmentation

深度学习论文: WinCLIP: Zero-/Few-Shot Anomaly Classification and Segmentation WinCLIP: Zero-/Few-Shot Anomaly Classification and Segmentation PDF: https://arxiv.org/pdf/2303.14814.pdf PyTorch代码: https://github.com/shanglianlm0525/CvPytorch PyTorch代码: h…

java使用swing制作桌面图形应用的实例教程

本篇文章主要讲解&#xff0c;java编程语言通过swing制作桌面图形应用的实例教程&#xff0c;通过一个简单的个人信息提交表单界面&#xff0c;让你了解swing的布局管理、窗口图标设置、编译和运行以及窗口菜单的设置。 日期&#xff1a;2023年8月25日 实际效果 弹出新窗口帮助…

一种分解多种信号模式非线性线性调频的方法研究(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…

Azure应用程序网关

文章目录 什么是应用程序网关实战演练创建虚拟网络创建虚拟机创建应用程序网关测试搭建结果 什么是应用程序网关 Azure应用程序网关是一种托管服务&#xff0c;用于提供安全、可缩放的 Web 应用程序前端点的应用程序传送控制和保护。它可以通过 SSL 终止、cookie 基于会话持久…

uniapp 安卓平台签名证书(.keystore)生成

安装JRE环境 下载jre安装包&#xff1a;https://www.oracle.com/java/technologies/downloads/#java8安装jre安装包时&#xff0c;记录安装目录(例:C:\Program Files\Java\jdk-20)打开命令行&#xff08;cmd&#xff09;&#xff0c;将JRE安装路径添加到系统环境变量 d: se…

使用vlc在线播放rtsp视频url

1. 2. 3. 工具链接&#xff1a; https://download.csdn.net/download/qq_43560721/88249440

数据分析案例-汽车客户信息数据可视化分析(文末送书)

&#x1f935;‍♂️ 个人主页&#xff1a;艾派森的个人主页 ✍&#x1f3fb;作者简介&#xff1a;Python学习者 &#x1f40b; 希望大家多多支持&#xff0c;我们一起进步&#xff01;&#x1f604; 如果文章对你有帮助的话&#xff0c; 欢迎评论 &#x1f4ac;点赞&#x1f4…

学习开发振弦采集模块的注意事项

学习开发振弦采集模块的注意事项 &#xff08;三河凡科科技/飞讯教学&#xff09;振弦采集模块是一种用来实时采集和处理振弦信号的电子设备&#xff0c;在工业、航空、医疗等领域都有广泛应用。学习开发振弦采集模块需要注意以下几点&#xff1a; 一、硬件选择 首先需要选择…

word文档中输入“打钩”的4种方法

我们利用Word来制作一些填写单、待办表、计划表类的文档时&#xff0c;都会输入一些特殊符号&#xff0c;比如方框内“打钩”的勾选符号&#xff0c;那么这个符号应该怎么输入呢&#xff1f; 接下来&#xff0c;我就给你们介绍几种简单实用的方法&#xff0c;其中第三种是小编…

Spark项目Java和Scala混合打包编译

文章目录 项目结构Pom完整文件编译查看 实际开发用有时候引用自己写的一些java工具类&#xff0c;但是整个项目是scala开发的spark程序&#xff0c;在项目打包时需要考虑到java和scala混合在一起编译。 今天看到之前很久之前写的一些打包编译文章&#xff0c;发现很多地方不太对…

【软件测试面试题】网页崩溃的原因是什么?如何排查?

网页崩溃的原因 1. 代码错误 网页中存在错误或不完善的代码可能导致崩溃。例如&#xff0c;语法错误、逻辑错误、变量未定义等。这些错误可能会导致浏览器无法正确解析网页&#xff0c;从而导致崩溃。 2. 资源加载问题 网页中引用的资源&#xff08;如CSS文件、JavaScript文…

【linux】2 make/Makefile和gitee

文章目录 一、Linux项目自动化构建工具-make/Makefile1.1 背景1.2 实例代码1.3 原理1.4 项目清理 二、linux下第一个小程序-进度条2.1 行缓冲区2.2 进度条 三、git以及gitee总结 ヾ(๑╹◡╹)&#xff89;" 人总要为过去的懒惰而付出代价ヾ(๑╹◡╹)&#xff89;" 一…

【点击新增一个下拉框 与前一个内容一样 但不能选同一个值】

点击新增一个下拉框 与前一个内容一样 但不能选同一个值 主要是看下拉选择el-option的disabled,注意不要混淆 <el-form label-width"120px" :model"form" ref"form" style"color: #fff"><template v-for"(trapolicy, i…

生成地图展示【Python思路】

# 1.导包 import json from pyecharts.charts import Map #导入关于编写地图的包 from pyechart.options import * #全局设置# 2.得到地图对象 map Map()# 3.打开事先准备好的JSON数据文件 f open("D:/Typora 记事本/notebook/Python/Exercise_data/疫情.txt",&…