力扣(LeetCode)之环形链表

题目：

给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。

[图片上传失败...(image-de0e1f-1694951323683)]

示例：

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

方法一：使用集合存储历史节点

我们可以遍历每一个链表中的节点，并将该节点的地址记录下来，如果发现下一个节点出现在了历史节点中，就说明该链表是一个环形链表。其具体代码如下：

# 利用集合记录历史节点
def fun1(head):
    set_arr = set()
    while head != None:
        if id(head) not in set_arr:
            set_arr.add(id(head))
        elif id(head) in set_arr:
            return True
        head = head.next
    return False

方法二：双指针法

使用快慢指针的方法，一个指针每次前进一个节点，第二个指针每次前进两个节点。如果快指针检测到当前节点或者是下一节点是None，就说明该链表不是循环链表，如果经过多次寻找后，发现快慢指针重合就说明该链表为循环链表，其具体代码如下：

# 双指针法 
def fun2(head):
    start = head 
    end = head.next

    while start != end: 
        if end == None or end.next == None:
            return False 
        start = start.next 
        end = end.next.next 
    return True