判断链表中是否存在环的方法及证明_判断链表是否存在环资源-CSDN文库

20 浏览量 2021-01-20 11:01:10 上传评论收藏 181KB PDF 举报

资源详情

资源评论

资源推荐

判断链表中是否存在环的方法及证明判断链表中是否存在环的方法及证明

一、判断链表中是否存在环的方法及证明一、判断链表中是否存在环的方法及证明

首先说明一点就是如果链中存在环，可能整个链是一个环，也可能是该链表的后面一部分形成了环。如何判断链表中是否存在环，经典的判断方法就是利用两个指向链表头节点的指首先说明一点就是如果链中存在环，可能整个链是一个环，也可能是该链表的后面一部分形成了环。如何判断链表中是否存在环，经典的判断方法就是利用两个指向链表头节点的指

针，同时移动，两个指针每次移动的节点数是不一样的，如果存在环，那么这两个指针随着移动次数的增加，肯定会某个节点相遇，否则移动快的指针会到率先达链表末尾，即不存针，同时移动，两个指针每次移动的节点数是不一样的，如果存在环，那么这两个指针随着移动次数的增加，肯定会某个节点相遇，否则移动快的指针会到率先达链表末尾，即不存

在环。在环。

有没有同学会疑惑：如果存在环，这两个移动速度不同的指针一定会相遇吗，两个指针速度值设置为多少合适呢？下面我们来证明一下：如果存在环，不管这两个指针的移动速度为有没有同学会疑惑：如果存在环，这两个移动速度不同的指针一定会相遇吗，两个指针速度值设置为多少合适呢？下面我们来证明一下：如果存在环，不管这两个指针的移动速度为

何，同时移动若干次后，这两个移动速度不同的指针肯定会相遇。证明过程如下：何，同时移动若干次后，这两个移动速度不同的指针肯定会相遇。证明过程如下：

（1）设两个指针为P1、P2，P1的移动速度为每次移动m个节点，P2的移动速度为每次移动n个节点，0 < m = 2)，链表剩余节点个数为L2（L2 >= 0）。

（2）我们利用假设法来证明，即假设会相遇，那么接下来我们要做的就是能否来找到一个次数K，这个K使下面两个条件a和b同时成立

a：(L2 + n*K) – (L2 + m*K) = h*L1 => K * (n – m) = h * L1 => K*(n-m)/L1为不小于1的整数，h为整数，代表P2节点比P1节点在环中多走的圈数。如果相遇了，那么P2节点肯定比P1

节点在环中都走了若干圈，所以推出这个等式成立；如果这个等式成立，也能表示P1和P2肯定能同时走到同一个节点上。

b：m*K >= L2 => K >= L2/m,这个条件之所以存在，是因为P1和P2肯定是在环内相遇，环外由于速度不同，是不可能相遇的，那么P1肯定进入环内了,那么环外的节点肯定都经历

了。

（3）在m、n、L2、L1给定的条件下，不管这四个变量的值为多少，我们都能找到符合a和b的一个最小整数，就是我们要找的次数K。比如m = 2，n= 3，L1 = 4，L2 = 3，我们要找

的K满足的条件是K/4为不小于1的整数，并且K >= 1.5，可得满足条件的最小整数为4，即同时移动4次，P1和P2会相遇。为了便于理解，我们以此为例，画图说明一下移动过程，如

下图所示：

综上可知：如果链表中存在环，那么两个指针初始指向位置均为头节点，并且两个指针移动速度只要不同并且均大于综上可知：如果链表中存在环，那么两个指针初始指向位置均为头节点，并且两个指针移动速度只要不同并且均大于0，那么同时移动若干次后，这两个指针肯定能够相遇。如果这，那么同时移动若干次后，这两个指针肯定能够相遇。如果这

样两个指针能够相遇，也说明链表中肯定存在环。样两个指针能够相遇，也说明链表中肯定存在环。

二、问题升华：如果链表中存在环，那么如何定位到链表中形成环的头节点呢？二、问题升华：如果链表中存在环，那么如何定位到链表中形成环的头节点呢？

该问题的算法是基于问题一的，但是对两指针的移动速度有了一个限制，就是两指针速度最好相差1，即n-m=1，两个指针相遇之后，我们只需把P1初始化为头节点，P2的位置保持

不变，然后两指针同时移动切每次均移动一个节点，那么这两个指针会再次相遇并且相遇时所处的节点就是环的头节点。

证明过程：我们设两节点相遇的时候，P1节点在环内所走的圈数是q1，P2节点在环内所走的圈数是q2，再设相遇所处的节点位置离环的头节点的距离为d，那么可得到下面两个等

式：

m*K = L2 + q1*L1 + d;

n*K = L2 + q2*L1 +d;

推导出n*(L2 + q1*L1 + d) = m*(L2 + q2*L1 +d) => d = (m*q2-n*q1)/(n-m)*L1 – L2，看到这个等式，我们设想，如果(m*q2-n*q1)/(n-m)为整数，那么如果P2再走L2步，刚好可以走到

环的头节点，而把P1初始化为链表的头节点，那么P1走L2步，也能刚好走到环的头节点。如何能让(m*q2-n*q1)/(n-m)为整数呢，那就是让n-m=1。

所以可得结论，如果想找到链表中环的头节点，则使用两个移动速度相差所以可得结论，如果想找到链表中环的头节点，则使用两个移动速度相差1的指针，先让它们相遇，然后在相遇的节点处，一个指针保持不变，另一个指针初始化为链表的头节点，的指针，先让它们相遇，然后在相遇的节点处，一个指针保持不变，另一个指针初始化为链表的头节点，

继续让他们同时移动，并且每次移动一个节点，那么它们定会在环的头节点相遇。继续让他们同时移动，并且每次移动一个节点，那么它们定会在环的头节点相遇。

闲来无事，对上述两个问题的解法加以证明，也好做到用起来心中无疑虑。

作者：Android海纳百川

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余0页未读，立即下载