判断单链表里面有没有环类问题

判断单链表里面有没有环系列问题

1.判断单链表是否有环

使用两个slow, fast指针从头开始扫描链表。指针slow 每次走1步,指针fast每次走2步。如果存在环,则指针slow、fast会相遇;如果不存在环,指针fast遇到NULL退出。

2.求有环单链表的环长

在环上相遇后,记录第一次相遇点为Pos,之后指针slow继续每次走1步,fast每次走2步。在下次相遇的时候fast比slow正好又多走了一圈,也就是多走的距离等于环长。

设从第一次相遇到第二次相遇,设slow走了len步,则fast走了2*len步,相遇时多走了一圈:
环长=2*len-len

3.求有环单链表的环连接点位置

第一次碰撞点Pos到连接点Join的距离 = 头指针到连接点Join的距离,因此,分别从第一次碰撞点Pos、头指针head开始走,相遇的那个点就是连接点。

  1. 当fast与slow相遇时,show肯定没有走完链表,而fast已经在还里走了n(n>= 1)圈,设环长为R。假设slow走了S步,那么fast走了2S步。fast的步数还等于S走的加上环里转的n圈,所以有:2S = S + nR。因此,S = nR。
  2. 设整个链表长为L,入口据相遇点lenB,起点到入口的距离为lenA。因为slow指针并没有走完一圈,所以:lenA + lenB = S,带入第一步的结果,有:lenA + lenB = nR = (n-1)R + R = (n-1)R + L - lenA;即:lenA = (n-1)R + L - lenA - lenB;即从头结点到入口的距离,等于转了(n-1)圈以后,相遇点到入口的距离。因此,我们可以在链表头、相遇点各设一个指针,每次各走一步,两个指针必定相遇,且相遇第一点为环入口点。

4.求有环单链表的链表长

2中求出了环长,3中求出了连接点的位置,相加就是链表长。

5.如何判断两个链表(不带环)是否相交

将其中的一个链表首尾相连,然后判断另一个链表是否带环即可。