python判断链表是否有环

思路：使用快慢指针，快指针每次走两步，慢指针每次走一步，如果有环，则一定会快慢指针指向同一结点；
假设环的长度为n,先让一个指针走n步，另一个再开始走，当他们指针指向同一结点时，该结点就是环入口点
(在快慢指针相遇之后，慢指针指向表头，快指针留在相遇点，二者以每次一步走直到相遇，该相遇点就是环入口结点)；

找到环入口结点之后，从入口结点开始遍历，每次遍历长度加一，如果下个结点等于入口结点，则返回长度

class ListNode(object):

    def __init__(self, dataval):

        self.dataval = dataval

        self.next = None

class JudgeLinkRing(object):

    def is_link_ring(self,head):

        if head is  None or head.next is None:

            return

        slow,fast=head,head

        while fast and fast.next:

            slow=slow.head

            fast=fast.next.next

            if slow==fast:

                slow=head

                while slow !=fast:

                    slow=slow.next

                    fast=fast.next

                fast1=fast

                fast=fast.next

                n=1

                while fast1 !=fast

                    fast=fast.next

                    n=n+1

                return slow,n

        return

巴特西

python判断链表是否有环

最新文章

热门文章