Offer150-23:链表中环的入口节点
题目描述:如果一个链表中包含环,找了环的入口节点。例如,在下图所示的链表中,环的入口节点是节点4。

分析:第一步需要确定一个链表中是否包含环,可以用快慢指针来解决这个问题。定义两个指针,同时从链表的头节点出发,一个指针一次走一步,另一个指针一次走两步。如果快指针追上了慢指针,说明链表中包含环路;如果快指针走到了链表的结尾(指向NULL)那么链表中就不包含环。
第二步是找到环的入口。我们还可以用两个指针来解决这个问题。先定义两个指针P1和P2指向链表的头节点。如果链表中的环有n个节点,则指针P1先在链表上向前移动n步,然后两个指针再以相同的速度向前移动。当P2指向环的入口节点时,P1也已经围绕着环走了一圈又回到了环的入口节点处。
那么我们就需要先获得环中的节点的数量n。开始我们判断链表中是否存在环路时,定义了两个指针,当快慢指针重合时,说明两个指针都在环中,链表中存在环路。这时,让一个指针再在环路里走一圈,同时统计它走过的步数,直到它再次回到出发位置,这时我们就可以得到整个环路中节点的数量n的大小。
代码:
ListNode* MeetingNode(ListNode* pHead){if(pHead == nullptr)return nullptr;ListNode* pSlow = pHead;ListNode* pFast = pSlow->m_pNext;while(pFast != nullptr && pSlow != nulltpr){if(pFast == pSlow)return pFast;pSlow = pSlow->m_pNext;pFast = pFast->m_pNext;if(pFast == nullptr){pFast = pFast->m_pNext;} }return nullptr;
}ListNode* EntryNodeOfLoop(ListNode* pHead){ListNode* meetingNode = MeetingNode(pHead);if(meetingNode == nullptr){return nullptr;}//得到环中节点的数目int nodesInLoop = 1;ListNode* pNode1 = meetingNode;while(pNode1->m_pNext != meetingNode){pNode1 = pNode1->m_pNext;++nodesInLoop;}//先移动pNode1,次数为环中节点的数目pNode1 = pHead;for(int i = 0;i < nodesInLoop;++i){pNode1 = pNode1->m_pNext;}//再移动pNode1和pNode2ListNode* pNode2 = pHead;while(pNode1 != pNode2){pNode1 = pNode1->m_pNext;pNode2 = pNode2->m_pNext;}return pNode1;
} 
相关文章:
Offer150-23:链表中环的入口节点
题目描述:如果一个链表中包含环,找了环的入口节点。例如,在下图所示的链表中,环的入口节点是节点4。 分析:第一步需要确定一个链表中是否包含环,可以用快慢指针来解决这个问题。定义两个指针,同时从链表的头…...
【linux】服务器创建RAID1
【linux】服务器创建RAID1 文章目录 【linux】服务器创建RAID1一、配置介绍raid介绍raid类型RAID 0:RAID 1:RAID 5:RAID 6:二、配置RAID硬件RAID:软件RAID:三、软件配置RAID1(以linux为例)1.先进入管理员模式2.安装mdadm工具3.创建raid1数组4.查看RAID数组状态5.格式化和挂载…...
记录自己Ubuntu加Nvidia驱动从入门到入土的一天
前言 记录一下自己这波澜壮阔的一天,遇到了很多问题,解决了很多问题,但是还有很多问题,终于在晚上的零点彻底放弃,重启windows。 安装乌班图 1.安装虚拟机 我开始什么操作系统的基础都没有,网上随便搜了…...
基于现有Docker镜像构建新的Docker镜像
1.拉取ubuntu 22.04的系统镜像 docker pull ubuntu:22.04 拉取成功后在DockerDesktop中可发现该镜像 2.启动刚才接取的ubuntu镜像 docker run --name Ubuntu22.04 -it -d -p 22:22 -p 80:80 -p 443:443 340d9b015b194dc6e2a13938944e0d016e57b9679963fdeb9ce021daac430221 启…...
Java 静态变量、静态代码块、普通代码块、构造方法的执行顺序
今天碰到这个问题,看了课程以及资料,做出解答。这是我自己绘制的图,按从上到下,从左到右的顺序执行。如有问题请联系我修正。 要点: 1、执行顺序分为两步,类加载和初始化阶段。 2、因为静态变量和静态代码块…...
计算机网络性能指标概述:速率、带宽、时延等
在计算机网络中,性能指标是衡量网络效率和质量的重要参数。本文将综合三篇关于计算机网络性能指标的文章,详细介绍速率、带宽、吞吐量、时延、时延带宽积、往返时延(RTT) 和利用率的概念及其在网络中的应用。 1. 速率(…...
众所周知沃尔玛1P是怎么运营?
沃尔玛的1P模式,即第一方供应商模式,是其独特的采购策略。在这种模式下,供应商先将商品卖给沃尔玛,由沃尔玛负责库存管理和销售。沃尔玛通过强大的采购和物流能力控制库存,确保商品品质,为客户提供更加…...
【Linux】静态库的制作和使用详解
💐 🌸 🌷 🍀 🌹 🌻 🌺 🍁 🍃 🍂 🌿 🍄🍝 🍛 🍤 📃个人主页 :阿然成长日记 …...
2.贪心算法.基础
2.贪心算法.基础 基础知识题目1.分发饼干2.摆动序列2.1.思路二:动态规划法 3.最大子序和4.买股票的最佳时机24.1.思路二:动态规划法4.2.买股票的最佳时机 5.跳跃游戏5.1.跳跃游戏2 6.K次取反后最大化的数组和7.加油站8.分发糖果 总结 基础知识 什么是贪…...
用Python轻松转换PDF为CSV
数据的可访问性和可操作性是数据管理的核心要素。PDF格式因其跨平台兼容性和版面固定性,在文档分享和打印方面表现出色,尤其适用于报表、调查结果等数据的存储。然而,PDF的非结构化特性限制了其在数据分析领域的应用。相比之下,CS…...
关于微信支付-商户平台:查询订单提示“查询失败:操作失败,请稍候重试”的分析
目录 引子 分析 应对 小结 引子 在开发和实施微信 JSAPI 支付的应用后,我们遇到了一些问题,订单的状态更新不正常,当然我们首先需要从自身寻找原因和完善解决问题的办法和方案。在支付的过程中,客户会给我们一些反馈…...
掌握【Python异常处理】:打造健壮代码的现代编程指南
目录 编辑 1. 什么是异常? 知识点 示例 小李的理解 2. 常见的内置异常类型 知识点 示例 小李的理解 3. 异常机制的意义 知识点 示例 小李的理解 4. 如何处理异常 知识点 示例 小李的理解 5. 抛出异常 知识点 示例 小李的理解 6. Python内置…...
STM32点灯闪烁
stm32c8t6引脚图 开发板引脚图 GPIO端口的每个位可以由软件分别配置成 多种模式。 ─ 输入浮空 ─ 输入上拉 ─ 输入下拉 ─ 模拟输入 ─ 开漏输出 ─ 推挽式输出 ─ 推挽式复用功能 ─ 开漏复用功能 配置GPIO端口步骤:开启时钟->使用结构体设置输出模式…...
Java-01-源码篇-04集合-05-SortedMap NavigableMap TreeMap
目录 一,SortedMap 二,NavigableMap 三,TreeMap 3.1 TreeMap 继承结构 3.2 TreeMap 属性 3.3 TreeMap 构造器 3.4 TreeMap 内部类 3.4.1 Values 3.4.2 KeySet 3.4.3 EntrySet 3.4.5 相关集合迭代器 3.4.5.1 PrivateEntryIterato…...
拥抱 AGI:PieDataCS 引领云原生数据计算系统新范式
自2023年后,人工智能技术进入了一个更为成熟和广泛应用的阶段,人工通用智能(AGI)这一概念也成为了科技界和产业界热议的焦点。本文将结合 AGI 时代背景,从架构设计到落地实践,详细介绍拓数派云原生数据计算…...
开放式耳机哪个品牌好?开放式耳机推荐
开放式耳机因其独特的设计,提供了更自然的听音体验和更好的环境声音感知,尤其适合长时间佩戴和户外运动使用,下面来推荐几款表现出色的开放式耳机: 悠律ringbuds pro凝声环(499元):凭借时尚潮流…...
kubernetes dashboard安装
1.查看符合自己版本的kubernetes Dashboard 比如我使用的是1.23.0版本 https://github.com/kubernetes/dashboard/releases?page5 对应版本 kubectl apply -f https://raw.githubusercontent.com/kubernetes/dashboard/v2.5.1/aio/deploy/recommended.yaml修改对应的yaml,…...
【MySQL】3.表的操作
表的操作 一.创建表二.查看表三.修改表四.删除表 一.创建表 create table [if not exists] tb_name( field1 datatype comment 说明, field2 datatype, field3 datatype) charsetutf8 collateutf8_gerenal_ci engineInnoDB//表的编码集,校验集如果不指定ÿ…...
十一、作业
1.从大到小输出 写代码将三个整数数按从大到小输出。 void Swap(int* px, int* py) {int tmp *px;*px *py;*py tmp;} int main() {int a 0;int b 0;int c 0;scanf("%d %d %d", &a, &b, &c);int n 0;if (a<b){Swap(&a, &b);}if (a &l…...
关于C#在WPF中如何使用“抽屉”控件
关于C#在WPF中如何使用“抽屉”控件 1.前提准备2.XAML代码3.对应的C#代码4.显示效果 1.前提准备 需要引用MaterialDesign控件库,关于如何引用,请参照文章——关于C#如何引用MaterialDesign控件库 2.XAML代码 <Window x:Class"MaterialDesign_…...
简易版抽奖活动的设计技术方案
1.前言 本技术方案旨在设计一套完整且可靠的抽奖活动逻辑,确保抽奖活动能够公平、公正、公开地进行,同时满足高并发访问、数据安全存储与高效处理等需求,为用户提供流畅的抽奖体验,助力业务顺利开展。本方案将涵盖抽奖活动的整体架构设计、核心流程逻辑、关键功能实现以及…...
工业安全零事故的智能守护者:一体化AI智能安防平台
前言: 通过AI视觉技术,为船厂提供全面的安全监控解决方案,涵盖交通违规检测、起重机轨道安全、非法入侵检测、盗窃防范、安全规范执行监控等多个方面,能够实现对应负责人反馈机制,并最终实现数据的统计报表。提升船厂…...
【位运算】消失的两个数字(hard)
消失的两个数字(hard) 题⽬描述:解法(位运算):Java 算法代码:更简便代码 题⽬链接:⾯试题 17.19. 消失的两个数字 题⽬描述: 给定⼀个数组,包含从 1 到 N 所有…...
ServerTrust 并非唯一
NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...
Python爬虫(一):爬虫伪装
一、网站防爬机制概述 在当今互联网环境中,具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类: 身份验证机制:直接将未经授权的爬虫阻挡在外反爬技术体系:通过各种技术手段增加爬虫获取数据的难度…...
汇编常见指令
汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX(不访问内存)XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...
Xen Server服务器释放磁盘空间
disk.sh #!/bin/bashcd /run/sr-mount/e54f0646-ae11-0457-b64f-eba4673b824c # 全部虚拟机物理磁盘文件存储 a$(ls -l | awk {print $NF} | cut -d. -f1) # 使用中的虚拟机物理磁盘文件 b$(xe vm-disk-list --multiple | grep uuid | awk {print $NF})printf "%s\n"…...
使用Spring AI和MCP协议构建图片搜索服务
目录 使用Spring AI和MCP协议构建图片搜索服务 引言 技术栈概览 项目架构设计 架构图 服务端开发 1. 创建Spring Boot项目 2. 实现图片搜索工具 3. 配置传输模式 Stdio模式(本地调用) SSE模式(远程调用) 4. 注册工具提…...
spring Security对RBAC及其ABAC的支持使用
RBAC (基于角色的访问控制) RBAC (Role-Based Access Control) 是 Spring Security 中最常用的权限模型,它将权限分配给角色,再将角色分配给用户。 RBAC 核心实现 1. 数据库设计 users roles permissions ------- ------…...
【FTP】ftp文件传输会丢包吗?批量几百个文件传输,有一些文件没有传输完整,如何解决?
FTP(File Transfer Protocol)本身是一个基于 TCP 的协议,理论上不会丢包。但 FTP 文件传输过程中仍可能出现文件不完整、丢失或损坏的情况,主要原因包括: ✅ 一、FTP传输可能“丢包”或文件不完整的原因 原因描述网络…...
