141. 环形链表(Easy)

题目描述

给定一个链表，判断链表中是否有环。

样例

题目解析

解法一【哈希表】

记录有没有走过，如果一直向前走，突然碰到走过的路，那么肯定是环路。空间复杂度过高

解法二【快慢指针】

龟兔法，参考 142. 环形链表 II(Medium)

• 和跑步一样，如果一个人跑的快，那么它迟早会 套圈 跑的慢的

• 我们设置慢的每次跑一步，快的每次跑两步，即有

  $ (m * 1) % n == (m * 2) % n$

  如 n 等于 4 的时候，m 等于 4 可以使得等号成立，即慢的人跑一圈正好和快的相遇

Python代码示例

解法一【哈希表】

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        if not head: return head 
        visited = set()
        while head:
            if head in visited: # 走过的路，那么肯定是环路
                return True 
            visited.add(head)
            head = head.next
        return False  

解法二【快慢指针】

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        if not head: return head 
        slow = fast = head 
        while fast and fast.next: # 如果爬到终点了
            slow = slow.next
            fast = fast.next.next
            if slow == fast:  # 如果相遇了
                return True
        return False