Leetcode|24. 两两交换链表中的节点 ● 19.删除链表的倒数第N个节点 ● 面试题 02.07. 链表相交 ● 142.环形链表II

24.

注意:涉及头节点的修改或者删除时,最好设置一个虚拟的头结点,方便简化代码,不必进行是否为头节点的的判断,简化code

class Solution {
public:ListNode* swapPairs(ListNode* head) {ListNode* dummyHead = new ListNode(0);//创建一个虚拟的头结点dummyHead->next = head;//建立联系ListNode* cur = dummyHead;//简化while(cur->next!=nullptr&&cur->next->next!=nullptr){//访问的合法性//记录临时地址的作用是方便找到结点,好进行新的连接ListNode* tmp = cur->next;//保存临时地址ListNode* tmp1 = cur->next->next->next;//保存临时地址cur->next = cur->next->next;//步骤一cur->next->next = tmp;//步骤二cur->next->next->next = tmp1;//步骤三cur = cur->next->next;//移动俩位,准备下一轮交换}ListNode* result = dummyHead->next;delete dummyHead;return result;}
};

 ListNode* cur = dummyHead;//这一步的操作也是始终知道头节点的位置,方便后续的链表输出

19.

class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode* dummyHead = new ListNode(0);dummyHead->next = head;ListNode* slow = dummyHead;ListNode* fast = dummyHead;while(n--&&fast!=nullptr){fast = fast->next;}fast = fast->next;while(fast!=nullptr){slow = slow->next;fast = fast->next;}ListNode* tmep = slow->next;slow->next = slow->next->next;delete tmep;//记得手动释放内存return dummyHead->next;}
};

面试题02.07(链表相交)

class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {ListNode* curA = headA;ListNode* curB = headB;int lenA = 0, lenB = 0;while (curA != NULL) { // 求链表A的长度lenA++;curA = curA->next;}while (curB != NULL) { // 求链表B的长度lenB++;curB = curB->next;}curA = headA;curB = headB;// 让curA为最长链表的头,lenA为其长度if (lenB > lenA) {swap (lenA, lenB);swap (curA, curB);}// 求长度差int gap = lenA - lenB;// 让curA和curB在同一起点上(末尾位置对齐)while (gap--) {curA = curA->next;}// 遍历curA 和 curB,遇到相同则直接返回while (curA != NULL) {if (curA == curB) {return curA;}curA = curA->next;curB = curB->next;}return NULL;}
};

142

class Solution {
public:ListNode *detectCycle(ListNode *head) {ListNode* fast = head;ListNode* slow = head;while(fast!=nullptr&&fast->next!=nullptr){slow = slow->next;fast = fast->next->next;//快慢指针相遇,此时从head和相遇点,同时查找直至相遇if(slow==fast){ListNode* index1 = fast;ListNode* index2 = head;while(index1!=index2){index1 = index1->next;index2 = index2->next;}return index1;//返回环的入口}}return nullptr;}
};

关于fast前进俩步的合法性判断:

为什么可以安全访问 fast->next->next?
链表的结构和指针移动的关系:在循环中,我们每次让 fast 走两步:fast = fast->next->next。
关键在于:只要我们能保证 fast 和 fast->next 都不为 nullptr,那么 fast->next->next 就一定是一个合法的访问。
fast != nullptr && fast->next != nullptr 的逻辑:如果 fast != nullptr 且 fast->next != nullptr 成立,意味着:
fast->next 是一个有效的节点(它的指针不为空)。
既然 fast->next 是一个有效节点,它的 next 域(即 fast->next->next)不一定为空,但一定是合法的访问。
如果 fast->next->next 是 nullptr,这只是意味着链表的终点到了,但访问它不会导致程序崩溃。
为什么不需要单独判断 fast->next->next?我们只需要判断两层的指针(fast 和 fast->next),因为算法的逻辑是:只有在 fast 能再往前移动时才继续循环。
如果 fast->next 是最后一个节点(即 fast->next->next == nullptr),那在本轮循环之后会退出,不会再执行下一次的 fast = fast->next->next。
总结
通过判断 fast != nullptr && fast->next != nullptr,我们确保了每次访问 fast->next->next 都是合法的。
即便 fast->next->next 是 nullptr,也只是说明链表结束了,并不会导致崩溃。下次循环时,会检测到不满足循环条件,程序会安全退出。
所以,这样的判断已经足够确保算法的安全性,不会出现对空指针的非法操作。

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

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

相关文章

Adobe Acrobat DC 打印PDF文件,没有打印出注释的解决方法

adobe acrobat在打印的时候,打印不出来注释内容(之前一直可以,突然就不行),升级版本、嵌入字体等等都试过,也在Google找了半天和问了GPT也么找着办法。 无奈之下,自己通过印前检查,…

ASP.NET Core8.0学习笔记(二十一)——EFCore关系配置API

一、关系配置API概述 当我们需要指定一个字段作为外键,而这个外键又不符合以上四种约定时,就需要在IEntityTypeConfiguration实现类(对应的配置类)中使用Fluent API直接配置外键。理论上可以通过API直接指定一个属性,…

HTTP快速入门

HTTP报文结构 HTTP 协议主要由三大部分组成: ● 起始行(start line):描述请求或响应的基本信息; ● 头部字段(header):使用 key-value 形式更详细地说明报文; ● 消息正…

vue 页面导出gif图片 img 导出gif 超简单~

1.首先需要新建一个文件件 新建gif文件夹。这两个文件在文章最后面需要可自提 2.出gif分为两种情况 第一种情况 页面是img标签,直接导出图片作为gif 第二种情况 页面是div标签,需要导出div里面的图片作为gif 2.1页面是img标签,直接导出图…

[论文阅读]Distilling ChatGPT for Explainable Automated Student Answer Assessment

Distilling ChatGPT for Explainable Automated Student Answer Assessment http://arxiv.org/abs/2305.12962 简要概述 文章的背景是 教育领域的学生答题评估,传统的评估需要高成本的人工,随着CHATGPT的发展,研究人员发现这种能够有效处理…

嵌入式QT中基本工程模板分析

大家好,今天主要来分享一下,如何分析一下QT的工程代码文件。 第一:QT工程分析

CentOS安装NVIDIA驱动、CUDA以及nvidia-container-toolkit

0.提前准备 0.1.更新yum源(以阿里为例) 0.1.1 备份当前的yum源 mv /etc/yum.repos.d/CentOS-Base.repo /etc/yum.repos.d/CentOS-Base.repo.backup 0.1.2 下载新的CentOS-Base.repo 到/etc/yum.repos.d/ CentOS 5 wget -O /etc/yum.repos.d/CentOS-Base…

Xilinx UltraScale系列FPGA纯verilog图像缩放,工程项目解决方案,提供2套工程源码和技术支持

目录 1、前言工程概述免责声明FPGA高端图像处理培训 2、相关方案推荐我这里已有的FPGA图像缩放方案本方案在Xilinx Artix7 系列FPGA上的应用本方案在Xilinx Kintex7 系列FPGA上的应用本方案在Xilinx Zynq7000 系列FPGA上的应用本方案在国产FPGA紫光同创系列上的应用本方案在国产…

Java爬虫API:获取商品详情数据的利器

为什么选择Java爬虫API 强大的库支持:Java拥有丰富的网络编程库,如Apache HttpClient、OkHttp等,这些库提供了强大的HTTP请求功能,使得发送请求和处理响应变得简单。高效的数据处理:Java的数据处理能力,结…

C语言:单链表(不带头节点)

目录 一、单链表概念 单链表的特点 二、单链表的实现 1、打印函数的实现 2、尾插函数的实现 3、全部函数的实现 总结: 一、单链表概念 链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。…

沈阳乐晟睿浩科技有限公司:引领抖音小店迈向新纪元

在当今数字化浪潮汹涌的时代,电子商务以其独特的魅力和无限潜力,正深刻改变着人们的消费习惯与商业模式。在这场变革中,沈阳乐晟睿浩科技有限公司凭借其敏锐的市场洞察力和卓越的技术实力,成为了抖音小店领域的佼佼者,…

Maven与Gradle的区别

Maven与Gradle是两种流行的构建工具,广泛用于Java项目的管理和构建。以下是它们的对比,包括官网、Windows 11配置环境、在IDEA中的相同点和不同点,以及它们各自的优缺点。 官网 Maven官网: https://maven.apache.orgGradle官网: https://gr…

Print Settings Page 打印设置页面

“打印设置”页面提供了设计时工具,用于自定义控制视图打印版本外观的打印选项。此页面如下图所示。 “选项”和“行为”选项卡式页面提供对视图打印选项的设计时访问,这些选项可通过其 GridView.OptionsPrint 属性或卡片视图的 CardView.OptionsPrint 进…

【Next.js 项目实战系列】07-分配 Issue 给用户

原文链接 CSDN 的排版/样式可能有问题,去我的博客查看原文系列吧,觉得有用的话,给我的库点个star,关注一下吧 上一篇【Next.js 项目实战系列】06-身份验证 分配 Issue 给用户 本节代码链接 Select Button​ # /app/issues/[i…

51单片机快速入门之 串行通信 2024/10/21

51单片机快速入门之 串行通信 并行通信: 好处:传输快 适合短距离通信弊端:占用大量io 接线形式为8对8 串行通信 异步通信: 数据一帧一帧传送,传输完一帧之后,可继续或者等待(等待时为高电平) 其帧细分为(图片来源) 起始位:数据帧开始,一定为 0 外部设备只有接受到 0 之后…

北京大学冯惠:与卓越者同行,方能更快的成长 | OceanBase数据库大赛获奖选手访谈

本文邀请2022 OceanBase 数据库大赛的季军,来自北京大学的冯惠同学,与我们分享如何寻找自己的兴趣;在一番经历后,对于产品与研发的职业方向观察;以及如何在学生时期提升个人专业能力,和参加数据库大赛的个人…

微信小程序用开发工具在本地真机调试可以正常访问摄像头,发布了授权后却无法访问摄像头,解决方案

今天开发上线了一个拍照的微信小程序&#xff0c;用uniapp的Vue3开发的&#xff0c;调用的camera组件&#xff0c;相关代码如下&#xff1a; <!-- 微信小程序相机组件 --><view v-if"showCamera" class"camera-container"><camera :device…

Ability内页面的跳转和数据传递(router和want显/隐跳转)

目录 案例:使用router完成页面跳转 1.创建一个Arkts项目 2.创建第二个页面 3.手动创建第三个页面 4.编写跳转路由 5.编写接受路由 6.编写返回上一个页面的代码 7.第三个界面代码完善 8.效果 案例:使用want启动Ability 1.创建一个新的项目 2.创建第二个界面 3.创建一个Ability 4…

23年408数据结构

第一题&#xff1a; 解析&#xff1a; 第一点&#xff0c;我们要知道顺序存储的特点&#xff1a;优点就是随用随取&#xff0c;就是你想要查询第几个元素可以直接查询出来&#xff0c;时间复杂度就是O(1)&#xff0c;缺点就是不适合删除和插入&#xff0c;因为每次删除和插入一…

android app执行shell命令视频课程补充android 10/11适配-千里马android

(https://blog.csdn.net/learnframework/article/details/120103471) https://blog.csdn.net/learnframework/article/details/120103471 hi&#xff0c;有学员在学习跨进程通信专题课程时候&#xff0c;在实战app执行一个shell命令的项目时候&#xff0c;对课程本身的android …