环形链表

🟢 Easy · 🏷️ 链表、双指针、快慢指针 · LeetCode#141

📖 题目

判断链表中是否存在环。

💡 思路

想象操场跑步：两个人同起点出发，一个跑得快一个跑得慢。跑道是环形的话，快的迟早会追上慢的（套圈）；跑道是直的，快的会先跑到终点。

快指针每次走两步，慢指针每次走一步。有环，快指针最终会追上慢指针；无环，快指针会先走到链表末尾（None）。

为什么一定会相遇？进入环之后，快指针每走一步都会比慢指针多缩短 1 的距离，缩到 0 就是相遇。

💻 代码

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        fast, slow = head, head
        while fast and fast.next:   # 快指针走两步，两个节点都得存在
            fast = fast.next.next
            slow = slow.next
            if fast == slow:        # 相遇 = 有环
                return True
        return False                # 走到头 = 无环

时间复杂度 O(n)，最多遍历两遍；空间复杂度 O(1)，只用了两个指针。