尧图网络 高端网站定制 · 原创设计
免费咨询热线
400-888-6620
免费获取方案
11.5 分享
本周分享环形链表定义单链表的某个节点的next不是null而是指向链表前面某个节点形成环遍历会无限循环。主要考察两点判断链表是否环如果有环如何找到这个环的入口一、判断是否有环快慢指针法分别定义 fast 和 slow 指针从头结点出发fast指针每次移动两个节点slow指针每次移动一个节点。因为fast是走两步slow是走一步其实相对于slow来说fast是一个节点一个节点的靠近slow的所以fast一定可以和slow重合。如果 fast 和 slow指针在途中相遇 说明这个链表有环。二、如何找到入口设头节点到入口处有x个节点入口到相遇处y个节点相遇处到入口z个节点快指针速度是慢指针速度的二倍2x y) x y n * (y z) #n为快指针绕的圈数推导得到x (n - 1) * (y z) z若令 n 1 得到 x z说明如果从头结点出发一个指针从相遇节点也出发一个指针这两个指针每次只走一个节点 那么这两个指针相遇的地方就是 环形入口的节点。即在相遇节点处定义一个指针index1在头结点处定一个指针index2。让index1和index2同时以每次一个节点速度移动 两指针相遇的地方为环形链表入口节点。e.g.力扣142环形链表II题目描述给定一个链表的头节点head返回链表开始入环的第一个节点。如果链表无环则返回null。如果链表中有某个节点可以通过连续跟踪next指针再次到达则链表中存在环。为了表示给定链表中的环评测系统内部使用整数pos来表示链表尾连接到链表中的位置索引从 0 开始。如果pos是-1则在该链表中没有环。注意pos不作为参数进行传递仅仅是为了标识链表的实际情况。不允许修改链表。代码示例structListNode*detectCycle(structListNode*head){structListNode*fasthead;structListNode*slowhead;while(fast!NULLfast-next!NULL){//判断是否有环fastfast-next-next;slowslow-next;if(fastslow){// 相交即有环开始找环形入口structListNode*ffast;structListNode*hhead;while(f!h){ff-next;hh-next;}returnh;//输出入口位置}}returnNULL;//链表中无环 输出NULL}链表相交定义 两个链表存在同一个节点对象内存地址相同该节点就是交点交点之后的所有节点都重合。只值相等不算相交相交链表一旦相交尾部一定相同核心思路利用双指针注意交点是指针相等创建两个指针curAcurB令A指向链表A的头结点B指向链表B的头结点求出两链表的长度并求出两链表长度差值让curA移动到和curB末尾对齐的位置比较curA和curB如果不相等同时向后移动当两者相等时找到交点e.g.力扣面试题02.07 链表相交题目描述给你两个单链表的头节点headA和headB请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点返回null。注意函数返回结果后链表必须保持其原始结构。代码示例structListNode*getIntersectionNode(structListNode*headA,structListNode*headB){structListNode*lNULL;structListNode*sNULL;intlenA0,lenB0,gap0;//求两个链表的长度lheadA;while(l!NULL){lenA;ll-next;}lheadB;while(l!NULL){lenB;ll-next;}//求长度差if(lenAlenB){lheadA;sheadB;gaplenA-lenB;}else{sheadA;lheadB;gaplenB-lenA;}//尾部对齐inti0;for(i0;igap;i){ll-next;}//移动检查相同元素while(l!NULL){if(ls){returnl;}ll-next;ss-next;}returnNULL;}双向链表链式储存结构的节点中只有一个指示直接后续的指针域由此从某个节点出发只能顺指针向后寻找其他节点。若要查找节点的直接前驱则必须从表头指针出发。为克服单链表这种单向性的缺点可利用双向链表。在双向链表中的节点有两个指针域一个指向直接后继另一个指向直接前驱。typedefintElemType;typedefstructnode{ElemType data;structnode*prev;//加入一个指向前驱的指针structnode*next;}Node;插入顺序先改新节点的 prev、next再修改相邻节点指针防止断链删除双向链表优势不用找前驱p-prev直接拿到前一个节点
RELATED

相关推荐

AI能替代小程序的程序员吗?真相比你想的更扎心

AI能替代小程序的程序员吗?真相比你想的更扎心

最近, 许多从事小程序开发的相关人员都表现出一种焦虑的情绪。因为人工智能编写代码的能力变得越来越强大, 只需要把具体的需求传递过去, 短短几秒钟的时间就可以生成一个完整的页面结构。此外, 它还能够自动检查出现的错误, 并为代码提供符合规范的注释内容。与此同时, 各种声…

📅 2026/11/6 3:43:18
WorkBuddy三大工作模式——Ask / Plan / Craft

WorkBuddy三大工作模式——Ask / Plan / Craft

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views …

📅 2026/11/6 3:43:18
AI 资讯日报 | 2026年11月3日:乌镇峰会聚焦AI开源开放,DeepSeek二轮融资1055亿元,腾讯混元Hyra 2.0发布,美团万亿参数LongCat-2.5登顶

AI 资讯日报 | 2026年11月3日:乌镇峰会聚焦AI开源开放,DeepSeek二轮融资1055亿元,腾讯混元Hyra 2.0发布,美团万亿参数LongCat-2.5登顶

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views …

📅 2026/11/6 3:43:18
MORE NEWS

更多资讯

📰

AI编程代理工程化协作:从GitHub Trending看团队落地

1. 近几周的 Trending 榜单到底在释放什么信号说实话,我每周一早上刷 GitHub Trending 已经成了固定动作,比看行业资讯还要准时。最近几周的榜单肉眼可见地变了一个调性:AI 编程代理类项目依然霸榜,但热度明显从“炫技”转向了“怎…

📰

信号量(Semaphore)原理与应用场景详解

1. Semaphore基础概念解析信号量(Semaphore)是操作系统和并发编程中的核心同步机制,由荷兰计算机科学家Dijkstra在1965年提出。它本质上是一个计数器,用于控制对共享资源的访问权限。与互斥锁(Mutex)不同,信号量允许多个线程同时访问资源&…

📰

Hermes Agent入门:安装、核心概念与首个实战

如果你和我一样,过去大半年被各种Agent框架的概念轮番轰炸——LangChain、AutoGPT、CrewAI、Dify——每个都说自己是下一代自动化神器,可真正下手跑一个能解决实际问题的Agent时,却往往卡在第一步。我最近仔细把Hermes Agent的资料和动手记录…

📰

物联网FPC天线选型与设计实践指南

1. 物联网模组天线选型的重要性与挑战在物联网设备设计中,天线性能往往决定着整个系统的通信质量。与传统刚性PCB天线相比,柔性印刷电路(FPC)天线因其独特的物理特性,正在成为越来越多物联网模组的首选方案。我曾在多个…

📰

一桶令牌的时间账本:四类限流算法的边界推演与Guava RateLimiter源码精读

目录 一、限流到底在管什么 (一)整点那一秒发生了什么 (二)速率、并发与排队:三种约束各管一段 1、速率限制:单位时间放进来多少 2、并发限制:此刻同时在办多少 3、排队限制:最多允许等多少 (三)否决式与整形式:被限住的请求去哪儿 (四)读懂限流参数的三把…

📰

Skywalking 9.4分布式链路追踪与性能监控实战指南

1. Skywalking概述与应用场景Skywalking是一款开源的APM(应用性能监控)系统,专为分布式系统设计,能够对微服务架构中的服务调用链路进行全链路追踪和性能分析。它通过探针无侵入式地采集数据,支持Java、.NET Core、Nod…

TODAY

今日更新

THIS WEEK

本周精选

THIS MONTH

本月热门

读完文章,想聊聊您的网站?

告诉我们您的行业与需求,资深顾问一对一梳理方案与报价,全程免费。

📞 💬