博客

如何判断单链表是否存在环

  • Post author:
  • Post category:其他


有一个单向链表，链表当中有可能出现“环”，就像题图这样。如何用程序判断出这个链表是有环链表？

不允许修改链表结构。

时间复杂度O(n)，空间复杂度O(1)。

方法一、穷举遍历

方法一：首先从头节点开始，依次遍历单链表的每一个节点。每遍历到一个新节点，就从头节点重新遍历新节点之前的所有节点，用新节点ID和此节点之前所有节点ID依次作比较。如果发现新节点之前的所有节点当中存在相同节点ID，则说明该节点被遍历过两次，链表有环；如果之前的所有节点当中不存在相同的节点，就继续遍历下一个新节点，继续重复刚才的操作。

例如这样的链表：A->B->C->D->B->C->D， 当遍历到节点D的时候，我们需要比较的是之前的节点A、B、C，不存在相同节点。这时候要遍历的下一个新节点是B，B之前的节点A、B、C、D中恰好也存在B，因此B出现了两次，判断出链表有环。

假设从链表头节点到入环点的距离是D，链表的环长是S。那么算法的时间复杂度是0+1+2+3+…+(D+S-1) = (D+S-1)

(D+S)/2 ， 可以简单地理解成 O(N

N)。而此算法没有创建额外存储空间，空间复杂度可以简单地理解成为O(1)。

方法二、哈希表缓存

****首先创建一个以节点ID为键的HashSet集合，用来存储曾经遍历过的节点。然后同样是从头节点开始，依次遍历单链表的每一个节点。每遍历到一个新节点，就用新节点和HashSet集合当中存储的节点作比较，如果发现HashSet当中存在相同节点ID，则说明链表有环，如果HashSet当中不存在相同的节点ID，就把这个新节点ID存入HashSet，之后进入下一节点，继续重复刚才的操作。

这个方法在流程上和方法一类似，本质的区别是使用了HashSet作为额外的缓存。

假设从链表头节点到入环点的距离是D，链表的环长是S。而每一次HashSet查找元素的时间复杂度是O(1), 所以总体的时间复杂度是1*(D+S)=D+S，可以简单理解为O(N)。而算法的空间复杂度还是D+S-1，可以简单地理解成O(N)。

方法三、快慢指针

首先创建两个指针1和2（在java里就是两个对象引用），同时指向这个链表的头节点。然后开始一个大循环，在循环体中，让指针1每次向下移动一个节点，让指针2每次向下移动两个节点，然后比较两个指针指向的节点是否相同。如果相同，则判断出链表有环，如果不同，则继续下一次循环。

例如链表A->B->C->D->B->C->D，两个指针最初都指向节点A，进入第一轮循环，指针1移动到了节点B，指针2移动到了C。第二轮循环，指针1移动到了节点C，指针2移动到了节点B。第三轮循环，指针1移动到了节点D，指针2移动到了节点D，此时两指针指向同一节点，判断出链表有环。

此方法也可以用一个更生动的例子来形容：在一个环形跑道上，两个运动员在同一地点起跑，一个运动员速度快，一个运动员速度慢。当两人跑了一段时间，速度快的运动员必然会从速度慢的运动员身后再次追上并超过，原因很简单，因为跑道是环形的。 

/**
 * 判断单链表是否存在环
 * @param head
 * @return
 */
public static <T> boolean isLoopList(ListNode<T> head){
    ListNode<T> slowPointer, fastPointer;
    
    //使用快慢指针，慢指针每次向前一步，快指针每次两步
    slowPointer = fastPointer = head;
    while(fastPointer != null && fastPointer.next != null){
        slowPointer = slowPointer.next;
        fastPointer = fastPointer.next.next;
        
        //两指针相遇则有环
        if(slowPointer == fastPointer){
            return true;
        }
    }
    return false;
}

假设从链表头节点到入环点的距离是D，链表的环长是S。那么循环会进行S次（为什么是S次，有心的同学可以自己揣摩下），可以简单理解为O（N）。除了两个指针以外，没有使用任何额外存储空间，所以空间复杂度是O（1）。

方法四、Set集合大小变化

评论中有 @长沙小辣椒 同学指出：还可以用 set 遍历链表，把节点放入set里，每次访问下个节点时，如果set长度不变，则跳出，说明有环。否则set长度+1，继续遍历。

该方法时间复杂度是O（N），空间复杂度上因为需要额外等数量的存储空间，所以空间复杂度是O（n）。

如何找出有环链表的入环点？

根据这篇文章：链表中环形的入口，我们来分析一下入环口和我们上面这个快慢指针相遇点的关系。

当fast若与slow相遇时，slow肯定没有走遍历完链表(不是一整个环，有开头部分，如上图)或者恰好遍历一圈(未做验证，看我的表格例子，在1处相遇)。于是我们从链表头、相遇点分别设一个指针，每次各走一步，两个指针必定相遇，且相遇第一点为环入口点(慢指针走了n步，第一次相遇在c点，对慢指针来说n=s+p，也就是说如果慢指针从c点再走n步，又会到c点，那么顺时针的CB距离是n-p=s，但是我们不知道s是几，那么当快指针此时在A点一步一步走，当快慢指针相遇时，相遇点恰好是圆环七点B(AB=CB=s))。 

/**
 * 找到有环链表的入口
 * @param head
 * @return
 */
public static <T> ListNode<T> findEntranceInLoopList(ListNode<T> head){
    ListNode<T> slowPointer, fastPointer;
    
    //使用快慢指针，慢指针每次向前一步，快指针每次两步
    boolean isLoop = false;
    slowPointer = fastPointer = head;
    while(fastPointer != null && fastPointer.next != null){
        slowPointer = slowPointer.next;
        fastPointer = fastPointer.next.next;
        
        //两指针相遇则有环
        if(slowPointer == fastPointer){
            isLoop = true;
            break;
        }
    }
    
    //一个指针从链表头开始，一个从相遇点开始，每次一步，再次相遇的点即是入口节点
    if(isLoop){
        slowPointer = head;
        while(fastPointer != null && fastPointer.next != null){
            //两指针相遇的点即是入口节点
            if(slowPointer == fastPointer){
                return slowPointer;
            }
            
            slowPointer = slowPointer.next;
            fastPointer = fastPointer.next;
        }
    }
    return null;
}

如何判断两个单链表是否相交，以及相交点？

方法一、直接法

直接判断第一个链表的每个结点是否在第二个链表中，时间复杂度为O(len1*len2)，耗时很大

方法二、利用计数

如果两个链表相交，则两个链表就会有共同的结点；而结点地址又是结点唯一标识。因而判断两个链表中是否存在地址一致的节点，就可以知道是否相交了。可以对第一 个链表的节点地址进行hash排序，建立hash表，然后针对第二个链表的每个节点的地址查询hash表，如果它在hash表中出现，则说明两个链表有共 同的结点。这个方法的时间复杂度为：O(max(len1+len2)；但同时还得增加O(len1)的存储空间存储哈希表。这样减少了时间复杂度，增加 了存储空间。

以链表节点地址为值，遍历第一个链表，使用Hash保存所有节点地址值，结束条件为到最后一个节点（无环）或Hash中该地址值已经存在（有环）。

再遍历第二个链表，判断节点地址值是否已经存在于上面创建的Hash表中。

这个方面可以解决题目中的所有情况，时间复杂度为O(m+n)，m和n分别是两个链表中节点数量。由于节点地址指针就是一个整型，假设链表都是在堆中动态创建的，可以使用堆的起始地址作为偏移量，以地址减去这个偏移量作为Hash函数

方法三、利用有环链表思路

对于两个没有环的链表相交于一节点，则在这个节点之后的所有结点都是两个链表所共有的。如果它们相交，则最后一个结点一定是共有的，则只需要判断最后一个结点是否相同即可。时间复杂度为O(len1+len2)。对于相交的第一个结点，则可求出两个链表的长度，然后用长的减去短的得到一个差值 K，然后让长的链表先遍历K个结点，然后两个链表再开始比较。

还可以这样：其中一个链表首尾相连，检测另外一个链表是否存在环，如果存在，则两个链表相交，而检测出来的依赖环入口即为相交的第一个

参考资料

漫画算法：如何判断链表有环？

判断两个单链表是否相交

数据结构面试 之 单链表是否有环及环入口点 附有最详细明了的图解

链表中环形的入口

【单链表】环的入口点 原理理解！

如何判断单链表是否有环、环的入口、环的长度和总长

如何寻找环入口？

我们先假设链表长度为N，环长度为n，那么我们就可以直接计算出快慢指针的相遇节点：

一、当n>=N/2时，快慢指针相遇第n个节点

证明，可推理出此时慢指针必然在环内，慢指针走了n步时，快指针走了2n步，比慢指针多走了n步，正好绕环一周回到 n节点，故此时相遇。

二、当n<N/2时，快慢指针相遇在 第（N-N%n）个节点

证明，由于 N%n<n，故此时慢指针已在环内，快指针比慢指针多走了（N-N%n）步，而（N-N%n）必然是 n的倍数，故 快指针 只比慢指针多绕环走了几整圈而已，此时快慢指针相遇。

那么我们说了上面这么多有什么用呢？我们实际上并不知道N和n的值为多少，但是我们通过判断有环的操作时实际上已经找到了快慢指针的相遇节点，也就是刚刚所说的 n节点或者（N-N%n）节点，我们简单点就称之为 m节点吧。

由刚才的分析可知m节点有个特点，那就是在m节点往下接着走m步最终还是回到m节点。那么我们利用这个特性，让快指针回到起点，慢指针仍然待在m节点，两个指针同时开始走，每次都只走一步。因为两个指针走m步后都会走到m节点，那么当它们第一次相遇时就必然是在环的起点。

还是比较好理解的是吧。哈哈看代码：

Node *getCircleHead(Node *node){


//先判读是否有环

if (hasCircle(node)) {

    Node *fast=node;
    Node *slow=node;
    
    //找到交点m
    do{
        fast=fast->next->next;
        slow=slow->next;
    }while (fast!=slow);
    
    //找环入口
    fast=node;
    while (fast!=slow) {
        fast=fast->next;
        slow=slow->next;
    }
    return fast;
}
return NULL;

}

附

如何推导出n和N-N%n呢？

首先我们假设链表长为N，环长度为n，非环部分长度m=N-n。

当慢指针走过m长度时，此时慢指针刚进入环，快指针走过2m。

由于快指针已经进入环内，可知快指针已经在环内走了2m-m=m步，当然由于环的长度为n，而且我们不知道m与n的大小关系，此时快指针应该在环的m%n的位置。

那么快指针还有差多少距离就能赶上慢指针了呢？快指针距离走完整个环有 (n-m%n)%n的长度（同时也是距离慢指针的距离），也就是说快指针再走2*((n-m%n)%n)就可以赶上慢指针了。

OK，我们再来看慢指针，根据上面的推导可以知道，慢指针走的距离为 d=m+(n-m%n)%n。

  1. 先看n-m%n，必然可知 0<n-m%n<=n，当且仅当m==n时，满足 n-m%n=n，所以将 m=n带入 d=m+(n-m%n)%n，得到 d=n;

  2. 由上面可知，当 m!=n时，0<n-m%n<n ，所以 (n-m%n)%n=n-m%n ，d= m+n-m%n =m+n-m%n，再分两种情况

    （1）m<n时，d=m+n-m=n;

    （2）m>n时，d=m+n-m%n=N-(N-n)%n=N-N%n;

最后综合上面结论可知

（1）m<=n时，d=n;

（2）m> n时，d=N-N%n;

推导稍微有点复杂，建议朋友们自己画个图，比较容易理解。

这个时候我们把d求出来以后，可以得到一个非常有意思的特性，从d节点开始往下再走d个节点，仍然能够走回到d点，证明：

当 m <= n 时，d = n，因为此时环的长度就为n，所以走d步还是回到原点。

当 m > n 时 ， d = m + n – m%n , 

                    d%n = m%n + n%n - m%n = 0，证明又回到了原点。

————————————————

版权声明：本文为CSDN博主「Aoruis」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。

原文链接：https://blog.csdn.net/lt623265189/article/details/104022580