惯性聚合 高效追踪和阅读你感兴趣的博客、新闻、科技资讯
阅读原文 在惯性聚合中打开

推荐订阅源

Recent Announcements
Recent Announcements
奇客Solidot–传递最新科技情报
奇客Solidot–传递最新科技情报
MongoDB | Blog
MongoDB | Blog
H
Help Net Security
钛媒体:引领未来商业与生活新知
钛媒体:引领未来商业与生活新知
人人都是产品经理
人人都是产品经理
freeCodeCamp Programming Tutorials: Python, JavaScript, Git & More
The GitHub Blog
The GitHub Blog
V
V2EX
Microsoft Security Blog
Microsoft Security Blog
V
Visual Studio Blog
A
About on SuperTechFans
博客园_首页
L
LangChain Blog
量子位
雷峰网
雷峰网
Cyber Security Advisories - MS-ISAC
Cyber Security Advisories - MS-ISAC
Jina AI
Jina AI
月光博客
月光博客
阮一峰的网络日志
阮一峰的网络日志
博客园 - 聂微东
Microsoft Azure Blog
Microsoft Azure Blog
M
MIT News - Artificial intelligence
N
Netflix TechBlog - Medium

博客园 - 大牛

第二次答疑 11.25晚C语言答疑 数据结构:矩阵程序C++实现 C语言:编程练习参考程序 C语言:循环作业参考程序 数据结构: 二叉树的建立与遍历源代码( 用c++ STL 实现) 题目: 从键盘输入若干个正整数, 按从小到大的顺序输出. 输入负数表示输入结束. 用链表实现. 微软的面试题及答案-超变态但是很经典[转] 数据结构-稀疏矩阵和树的程序 部分面试题 算法题 辩论题 计算机语言兴趣小组水平测试参考答案 C语言活动小组的练习题 有关C语言的随机函数的解答 有关 alter tablespace begin backup 学生问的一道C语言题目 一篇有关教育的文章 答学生问,并不专业地
一道数据结构&算法题
大牛 · 2005-12-28 · via 博客园 - 大牛

现有一个链表,证明如果存在环,则:使用两个指针同时前进但步长不一样,则能够在有限步之后能够相逢。

题目的意思是我归纳出来的,我的解题思路是这样的:

能够相下逢的意思是:
在走了x步以后,x×S1 和 x×S2 对N同余,其中S1、S2为两个指针的步长,N为环的长度。

(x*s1) %N = (x*s2) %N
等价于:
x*s1 - a*N = x*s2 - b*N
=> x = ( (a - b)*N ) / ( s1 - s2 )

a, b 为指针所走的圈数。a 和b之间的关系于s1,s2有关。
a/b = s1 / s2
这样,上式可改写为:
x = ( a*(1 - s2/s1)*N ) / (s1 - s2)