【数据结构和算法初阶(C语言)】带环链表问题详解(快慢指针的烧脑应用)

目录

1.铺垫-----带环链表基本了解

2. 题目:环形链表

 

3.环形链表||  

​编辑 3.1题解1

3.2  题解2

4.总结


1.铺垫-----带环链表基本了解

  环形链表题目启迪:

环形链表特点:遍历链表会出现一模一样的地址

 

2. 题目:环形链表

给你一个链表的头节点 head ,判断链表中是否有环。

如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。注意:pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ,则返回 true 。 否则,返回 false 。

. - 力扣(LeetCode). - 备战技术面试?力扣提供海量技术面试资源,帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。icon-default.png?t=N7T8https://leetcode.cn/problems/linked-list-cycle/

 启迪:

首先,如果是循环链表这种特殊的带环指针,那么当我们用一个指针来遍历这个链表,就会有遍历指针等于头节点停下来,就判断有环存在。

那么对于其他带环链表来说,无法判断在哪一个节点开始是环的开始节点,如何找得到两个相等的指针呢。

这里使用快慢指针的思想,既定义两个指针,如上图所表现,最终两个指针都会进入我们的环形链表中,不断的跑,如果两者的速度差控制合适,那么总有一瞬间两者就会相遇,当两者相遇就可以说明这个链表带环。那么关键在于快慢指针之间的速度差该设置为多少。

 首先,我们可以猜想快指针的速度是慢指针速度的两倍,就是说慢指针一次走一步,快指针一次走两步:

那么当我们的慢指针进入环时,如果两者目前没有相遇,那么是不是应该是快指针在追击慢指针,设慢指针刚入环时他们之间的距离为N

如果速度是三倍,同样的分析:
当慢指针进入环时:设两者的距离为N,

那么每走一次,快指针走三步,慢指针走一步,二者之间距离减少2;

N-2   N-4  N-6     N-8

如果N是偶数,最后就可以追上

如果N是奇数,最后会减为-1,就是二者错过,此时设环的周长为C,那么两者相距c -1

每移动一次距离-2,

设c-1为N

N-2   N-4  N-6     N-8.............

如果N是偶数,最后就可以追上

如果N是奇数,最后会减为-1,就是二者错过,此时设环的周长为C,那么两者相距c -1

那么如果c-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;}

 

 

3.环形链表||  

 

给定一个链表的头节点  head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null

如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos 是 -1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。

不允许修改 链表。

. - 力扣(LeetCode). - 备战技术面试?力扣提供海量技术面试资源,帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。icon-default.png?t=N7T8https://leetcode.cn/problems/linked-list-cycle-ii/

 3.1题解1

 结论:从相遇点定义一个指针,在头结点出发一个指针,两个指针速率相同,最后会在环的入点相遇

 

 

 

struct ListNode *detectCycle(struct ListNode *head) {struct ListNode * slow = head;struct ListNode *cur  = head;struct ListNode * fast = head;while(fast&&fast->next){slow = slow->next;fast = fast->next->next;if(slow == fast){//相遇了struct ListNode * meet = slow;//让相遇这里的指针和头结点的指针走while(meet != cur){cur = cur->next;meet = meet->next;}return cur;}}return NULL;}

 

3.2  题解2

 

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {struct ListNode * cura = headA,*curb = headB;int lena = 1;int lenb = 1;while(cura->next){cura = cura->next;lena++;//计算链表a的长度}while(curb->next){curb = curb->next;lenb++;//计算链表b的长度}//如果两个链表相交,那么尾结点的地址一定相等//所以这里就可以判断一下两个链表是否相交if(cura != curb){return NULL;}int gap = abs(lena-lenb);//计算两个链表之间的差值,用来绝对值struct ListNode*longst = headA,*shortlist = headB;if(lena<lenb){longst = headB;shortlist = headA;}while(gap--){longst = longst->next;//长的先走差距步}//同时找交点while(longst != shortlist){longst = longst->next;shortlist = shortlist->next;}return longst;
}
struct ListNode *detectCycle(struct ListNode *head) {struct ListNode * slow = head;struct ListNode *cur  = head;struct ListNode * fast = head;while(fast&&fast->next){slow = slow->next;fast = fast->next->next;if(slow == fast){//相遇了struct ListNode * meet = slow;//让相遇这里的指针和头结点的指针走struct ListNode * newnode = meet->next;meet->next = NULL;return   getIntersectionNode(head,newnode);}}return NULL;}

 

4.总结

带环链表的题目涉及到数学分析,从解题的过程中我们也能感知到,可以结合图解多看一下代码,结合理解。以上就是本期的所有内容,知识含量蛮多,大家可以配合解释和原码运行理解。创作不易,大家如果觉得还可以的话,欢迎大家三连,有问题的地方欢迎大家指正,一起交流学习,一起成长,我是Nicn,正在c++方向前行的奋斗者,数据结构内容持续更新中,感谢大家的关注与喜欢。

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

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

相关文章

C++输入输出(I\O)

我们知道C是由C语言发展而来的&#xff0c;几乎完全兼容C语言&#xff0c;换句话说&#xff0c;你可以在C里面编译C语言代码。如下图: C语言是面向过程的语言&#xff0c;C在C语言之上增加了面向对象以及泛型编程机制&#xff0c;因此C更适合中大型程序的开发&#xff0c;然而C…

Linux 设置快捷命令

以ll命令为例&#xff1a; 在 Linux 系统上&#xff0c;ll 命令通常不是一个独立的程序&#xff0c;而是 ls 命令的一个别名。 这个别名通常在用户的 shell 配置文件中定义&#xff0c;比如 .bashrc 或 .bash_aliases 文件中。 要在 Debian 上启用 ll 命令&#xff0c;你可以按…

李沐动手学习深度学习——4.5练习

1. 在本节的估计问题中使用λ的值进行实验。绘制训练和测试精度关于λ的函数。观察到了什么&#xff1f; 修改代码运行如图所示&#xff0c;可以发现对于lamda值的变化而言&#xff0c;对于训练loss和测试loss的影响不大。但是如果λ 太大后&#xff0c;train和test的loss会变得…

Cyber RT 组件

场景 无人车上的传感器数据可能需要被融合&#xff0c;比如在车辆上安装了多颗雷达&#xff0c;不同雷达由于安装位置与自身参数差异&#xff0c;可探测的角度、范围、距离等都是不尽相同的&#xff0c;现在需要将不同雷达感知到的数据融合在一起以建立车辆所处的完整环境&…

机器学习-面经(part5、KNN和SVM)

8. KNN 8.1 简述一下KNN算法的原理? 一句话概括:KNN的原理就是当预测一个新的值x的时候,根据它距离最近的K个点是什么类别来判断x属于哪个类别 工作原理:存在一个样本数据集合,也称作为训练样本集,并且样本集中每个数据都存在标签,即我们知道样本集中每一个数…

TypeError: the JSON object must be str, bytes or bytearray, not dict

参考文章&#xff1a;https://blog.csdn.net/yuan2019035055/article/details/124934362 Python基础系列&#xff08;一&#xff09;搞懂json数据解析与字典之间的关系 代码&#xff1a; 报错信息: TypeError: the JSON object must be str, bytes or bytearray, not dict …

局域网如何远程?

局域网远程一直是许多用户在处理远程连接需求时面临的一个难题。随着技术的不断进步&#xff0c;一种名为“天联”的组网解决方案应运而生。天联组网具有操作简单、跨平台应用、无网络要求以及独创的安全加速方案等独特优势&#xff0c;在解决各行业客户的远程连接需求方面发挥…

解决ipconfig不能使用的问题

问题所示&#xff1a;ipconfig不是内部或外部命令&#xff0c;也不是可运行的程序或批处理文件。 解决办法如下: 1.右击此电脑&#xff0c;点击属性设置&#xff1a; 2.点击高级系统设置 3.点击进入环境变量 4.在系统变量中进行设置&#xff0c;双击PATH进行配置 5.点击新建&am…

【如何在Docker中,修改已经挂载的卷(Volume)】

曾梦想执剑走天涯&#xff0c;我是程序猿【AK】 提示&#xff1a;添加投票&#xff01;&#xff01;&#xff01; 目录 简述概要知识图谱 简述概要 如何在Docker中&#xff0c;修改已经挂载的卷&#xff08;Volume&#xff09; 知识图谱 在Docker中&#xff0c;修改已经挂载…

matlab 提取分割位于多边形区域边缘内部或边缘上的点

[in,on] = inpolygon(xq,yq,xv,yv) xv 和 yv 为定义的多边形区域的,如xv = [1 4 4 1 1 ];yv = [1 1 4 4 1 ];注意最后一个数字与第一个重复,保证多边形闭合; xq 和 yq 为待查询的点in:在多边形内部和边缘的点序号on:仅在多边形边缘的点序号 提取分割方法: matrix=[xq yq…

智能汽车加速车规级存储应用DS2431P+TR 汽车级EEPROM 存储器IC

DS2431PT&R是一款1024位1-Wire EEPROM芯片&#xff0c;由四页存储区组成&#xff0c;每页256位。数据先被写入一个8字节暂存器中&#xff0c;经校验后复制到EEPROM存储器。该器件的特点是&#xff0c;四页存储区相互独立&#xff0c;可以单独进行写保护或进入EPROM仿真模式…

折线图实现柱状阴影背景的demo

这个是一个由官网的基础折线图实现的流程&#xff0c;将涉及到的知识点附上个人浅薄的见解&#xff0c;源码在最后&#xff0c;需要的可自取。 折线图 成果展示代码注解参数backgroundColordataZoomlegendtitlexAxisyAxisgridseries 源码 成果展示 官网的基础折线图&#xff…

【Python】OpenCV-使用ResNet50进行图像分类

使用ResNet50进行图像分类 如何使用ResNet50模型对图像进行分类。 import os import cv2 import numpy as np from tensorflow.keras.applications.resnet50 import ResNet50, preprocess_input, decode_predictions from tensorflow.keras.preprocessing import image# 设置…

计算机网络物理层知识点总结

本篇博客是基于谢希仁编写的《计算机网络》和王道考研视频总结出来的知识点&#xff0c;本篇总结的主要知识点是第二章的物理层。上一章的传送门&#xff1a;计算机网络体系结构-CSDN博客 通信基础 物理层概念 物理层解决如何在连接各种计算机的传输媒体上传输数据比特流&am…

leetcode刷题日记-K个一组翻转(链表)

题目描述 解题思路 第一种解法&#xff0c;也是我们常用的一种解题方法&#xff0c;首先遍历一遍列表&#xff0c;将列表中的val的值存放到数组中&#xff0c;然后按照要求对数组进行排序&#xff0c;排序之后&#xff0c;我们重新定义节点&#xff0c;将节点按照排完序的结果…

如何远程连接MySQL数据库?

在现代互联网时代&#xff0c;远程连接MySQL数据库成为了许多开发者和管理员必备的技能。这不仅方便了数据的共享和管理&#xff0c;还可以使多个团队在全球范围内协同工作。本文将介绍如何通过天联组网实现远程连接MySQL数据库&#xff0c;并实现高效的信息远程通信。 天联组网…

力扣hot100:1.两数之和

输入中可能存在重复值 。 分析&#xff1a; 本题需要返回的是数组下标&#xff0c;因此如果需要使用排序然后双指针的话&#xff0c;需要用到哈希表&#xff0c;但是由于输入中可能存在重复值&#xff0c;因此哈希表的value值必须是vector<int>。 使用双指针求目标值targ…

OpenDDS 跨主机通信配置与实现(C++和Java)

目录 1、编写一个示例1.1、IDL接口定义1.2、MPC文件介绍1.3、生成解决方案 2、通讯测试2.1、使用repo server 通讯2.2、使用repo ipport方式2.3、对等发现face 1、编写一个示例 1.1、IDL接口定义 假设我们现在有以下结构&#xff1a; struct MessagerOne { int subject_id; …

CMU 10-414/714: Deep Learning Systems --hw0

hw0 宏观上的步骤: softmax loss: 实现softmax loss代码 概念 softmax就是将结果映射到0~1之间,且所有结果相加为1(概率形式)cross-entropy loss就是计算 p ( x ) log ⁡ q ( x ) p(x)\log {q(x)} p(x)logq(x),此值可用于衡量实际输出与期望输出的距离,进而衡量预测模…

各种排序算法

文章目录 1. 基于比较排序算法总结2. 非比较排序算法 1. 基于比较排序算法总结 2. 非比较排序算法