floyd判断列表是否有cycle

一个列表,不使用额外空间,如何判定是否存在cycle(循环)呢?

一个简单有效的算法为floyd算法,可以理解为一个乌龟和一个兔子赛跑,如果它们跑的是一个循环的圆圈,那么乌龟一定会追上兔子。

该算法设置一个fast结点和slow结点,fast每次向前移动两步,slow每次向前一步,每次移动后判定fast是否等于slow。如果相等,则说明存在圆环。

该算法完备性可以简单解释如下,每一次行走,相当于fast结点走了一步,slow结点不动,所以,经过n步(n为循环的节点数),两结点一定相遇。

python代码如下

class Solution(object):
    def hasCycle(self, head):
        “””
        :type head: ListNode
        :rtype: bool
        “””
        fast=slow=head
        while (fast and fast.next):
            fast=fast.next.next
            slow=slow.next
            if(fast==slow):
                return True
        return False

    原文作者:Mu-Shen
    原文地址: https://blog.csdn.net/a5139515/article/details/78192426
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞