算法题: 判断环形链表

📌 给你一个链表的头节点 head ，判断链表中是否有环。

def has_cycle_set(head):
    """使用集合或者哈希表，记录访问过的节点，若再次出现则有环
       1. 时间复杂度：O(N)O(N)，其中 NN 是链表中的节点数。最坏情况下我们需要遍历每个节点一次。
       2. 空间复杂度：O(N)O(N)，其中 NN 是链表中的节点数。主要为哈希表的开销，最坏情况下我们需要将每个节点插入到哈希表中一次。
    """
    seen = set()
    while head:
        if head in seen:
            return True
        else:
            seen.add(head)
        head = head.next
    return False

def has_cycle_fast_slow_pointer(head):
    """
    使用两个指针，一快一慢遍历链表，如果链表存在环，则最终快指针肯定会与慢指针相遇
    """
    # 如果头节点为空或者头结点没有下一个结点，则不存在环
    if not head or not head.next:
        return False
    
    # 定义两个快慢指针遍历，这里快指针比慢指针先出发
    # 不是同一个位置出发，这么写的原因是 while 的条件需要一开始
    # 处于不满足的情况
    slow = head
    fast = head.next

    while slow != fast:
        # 如果 fast 为空或没有下一个结点，说明遍历到了链表尾部
        # 说明不存在环，有环的话会循环到前面的结点
        if not fast or not fast.next:
            return False

        # 移动快慢指针
        fast = fast.next.next
        slow = slow.next

    # while 后的条件为 True，即 slow == fast, 说明存在环
    # 此时 slow 指向的结点 == fast 指向的结点
    return True

总结：

链表的访问是从第一个结点开始的，不要用数组的思维去理解链表

在链表操作中，通常会创建一个伪结点，又称 dummy 结点，使用 dummy 结点的好处是 1. 在链表初始化的时候，没有合适的结点可以使用，用一个伪结点开始初始化比较方便，但需要注意在返回的时候需要返回 dummy.next. 2. 可以使用 while node 或者是 if node ，来判断某个结点是否有 next