网站新闻关键词wordpress页面移动端

网站新闻关键词,wordpress页面移动端,可以做免费推广的网站,中国工程信息网站1.如何判断有头结点的链表是否有环快#xff08;fast#xff09;慢#xff08;slow#xff09;指针#xff1a;1.设置快慢指针#xff0c;同时从头结点的后继节点#xff08;第一个有效节点#xff09;出发。2.快指针每次走两步#xff0c;慢指针每次走一步#xff0…1.如何判断有头结点的链表是否有环快fast慢slow指针1.设置快慢指针同时从头结点的后继节点第一个有效节点出发。2.快指针每次走两步慢指针每次走一步当快慢指针相遇时即说明存在环利用速度差制造 “有环必相遇” 的条件核心原理若链表有环当slow进入环后fast已经在环内绕圈由于相对速度是 1fast与slow的距离会每轮缩小 1 步最终必然相遇不会 “跳过” 对方。快慢指针的相对速度 1 步 / 轮fast 每轮比 slow 多走 1 步无论 slow 进入环时与 fast 的初始距离是n每轮距离都会减少 1最终必然缩小到 0相遇若选其他步数如 fast3 步、slow1 步相对速度 2当环长为偶数、初始距离为奇数时距离会一直是奇数如 1→-1→1→-1模环长后永远无法为 0导致 “有环但永远不相遇”2 步 1 步是唯一能保证 “有环必相遇” 的最小步数组合也是效率最高的遍历次数最少。易错点补充豆包不要 “先移动指针再判断相遇”若先移动再比较初始时slowfast首元节点会被跳过但逻辑仍成立但先判断再移动会误判初始位置为 “有环”比如只有头结点 1 个节点时初始 slowfast 首元节点直接返回 1错误头结点的 “空指针检查” 必须优先工业级代码中第一步要判断head是否为 NULL避免后续访问head-next崩溃。流程图如下图片中6和7的位置应该互换抱歉创作的时候没有仔细看核心代码实现2.如何找到循环链表的入口进入环的环口第一步先确定环中有多少结点环的长度是第一次相遇时 fast 比 slow 多走的步数通常为 1 倍环长即在第一次相遇后可以创建变量count1记录环中结点的个数在再次相遇之前fast 与 slow 每挪动一个单位长度count 值就加一这样的同时也意味着count的值可作为快慢指针的依据第二步重新让fast和slow指向头结点fast比slow先走count步然后再同时走此时fast和slow的步长均为1步为什么这样能够找到环口豆包补充假设头节点到环入口的距离为L环入口到相遇点的距离为X环长为count。第一次相遇时slow走的总路程L X由前面的推导slow走的总路程 环长 →L X count→L count - X。当fast先走count步后fast的位置count总步数L X (count - L - X)绕环的部分→ 等价于fast走到 “相遇点”再往回退X步即环入口位置此时slow从头节点出发fast从 “count 步位置” 出发两者同速步长 1走L步后slow走到环入口走了Lfast从count步位置走L步 →count L (L X) (count - X) L L环内绕圈后也到达环入口因此两者会在环入口相遇。第三步再次相遇的结点即为环的入口流程图蓝色标注的内容即为第二步的内容核心代码实现图源b站逊哥这里的循环条件p-next ! slow解读为当p-next slow时即p的下一个结点回到相遇点此时p刚好绕环走了一圈避免掉再记一次相遇点造成环的结点计数错误若为p slow会造成循环条件从一开始就不成立count的数值永远为初始值1无法正常统计环的长度。