IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 链表有环,快慢指针走3步可以吗 -> 正文阅读

[数据结构与算法]链表有环,快慢指针走3步可以吗

先说结果,可以走三步,但没必要,反而会影响效率。

下面是推导过程,摘自stackflow。
在这里插入图片描述
设非环的部分s步,环t步,快指针速度是慢指针的k倍,快慢指针在距离环开头的 j 步处相遇。

那么,相遇时,慢指针走了s+j,快指针走了s + j + m * t,(m是快指针在环中的圈数)

此时,快指针走的距离时慢指针的k倍,则有等式:

k * (s + j) = s + j + m * t

变换一下:

s + j =  (m / k-1)t

根据上面的公式可知,等式左边是慢指针走的步数,是等式右边环长度的倍数,慢指针步数s + j是整数,环长度t也是整数,(m / k-1)中,k-1>0,在其他量都确定的情况下,保持(m / k-1)不变的话,分母k-1越小,则分子m也越小,对应快指针在环中走的圈数m也越小,k=2,3,4···,其中k=2时,m最小,即最快相遇,这样效率最高。

环形链表入环点

leetcode142题:https://leetcode.cn/problems/linked-list-cycle-ii/
同样可以推导一下。
快慢指针走得步数:f=2(s+j)
快慢指针相遇时,f=(s+j) +mt(公式含义同最上)
则可以得出s+j=mt,相遇时绕的圈数刚好等于慢指针走的步数。
假设此时再走 l 步到达环的入口,会与走s步的指针相遇,有mt+l=mt+s (环中加mt还是原点)
合并上面两个式子后得 l=s,即再走非环的部分s步即可到入环点。

如图,紫色节点相遇后,假设快指针再绕一圈到这里,走了b+c,而慢指针走到这里,走了a+b,其中b为公共部分,则a=c。
在这里插入图片描述

总结:相遇时,慢指针走的步数刚好为快指针在环中绕圈的总步数,距离入环点的步数刚好是非环路径步数。

参考链接:https://stackoverflow.com/questions/5130246/why-increase-pointer-by-two-while-finding-loop-in-linked-list-why-not-3-4-5

  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2022-06-29 19:19:22  更:2022-06-29 19:21:11 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年3日历 -2024/3/29 20:32:34-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码