如何判断链表有环的三种解法(Python)

一、问题描述
二、解题思路
三、最优解的代码实现

一、问题描述

有一个单向链表，链表中有可能出现环，如何判断链表是否有环？

二、解题思路

方法一：
首先从头节点开始，依次遍历单链表中的每一个节点。每遍历一个新节点，就从头检查新节点之前的所有结点，用新节点和此结点之前的所有结点依次作比较。如果发现该节点和之前的某个节点相同，则说明该节点被遍历过两次，链表有环；如果之前的所有结点中不存在与新节点相同的结点，就继续遍历下一个新节点，继续重复刚刚的操作。
该方法的时间复杂度为O(n^2)，空间复杂度为O(1)

方法二：
首先创建一个结点集合，用来存储曾经遍历过的结点。同样是从头节点开始，依次遍历单链表中的每一个结点。每遍历一个新节点，就用新节点和集合中的结点进行比较，如果集合中存在与之相同的结点，则说明链表有环。如果不存在，就把该节点存入集合中，继续重复刚刚的操作。
该方法的时间复杂度为O(n)，空间复杂度为O(n)

方法三：
首先创建两个指针p1、p2(在Python中就是两个对象引用)，让它们同时指向这个链表的头节点。然后开始一个大循环，在循环体中，让指针p1每次向后移动一个节点，让指针p2每次向后移动两个节点，然后比较两个指针指向的节点是否相同。如果相同，则可以判断出链表有环，如果不同，则继续下一次循环。
这种方法类似于追及问题。
在一个环形跑道上，两个运动员从同一起点跑，一个运动员速度快，一个运动员速度慢。当两个人跑了一段时间后，速度快的运动员就会再次追上并且超过速度慢的运动员。
该方法的时间复杂度为O(n)，空间复杂度为O(1)

三、最优解的代码实现

class Node:
    def __init__(self,data):
        self.data=data
        self.next=None

def isCycle(head):
    p1=head
    p2=head
    while p1 is not None and p2.next is not None:
        p1=p1.next
        p2=p2.next.next
        if p1==p2:
            return True
    return False

node1=Node(4)
node2=Node(3)
node3=Node(5)
node4=Node(1)
node5=Node(8)
node1.next=node2
node2.next=node3
node3.next=node4
node4.next=node5
node5.next=node2
print(isCycle(node1))