คุณจะตรวจจับลูปโดยใช้เต่าและกระต่ายของ Floyd ได้อย่างไร

Question

Accepted Answer

**การตรวจจับลูปของ Floyd** ค้นหาลูปในลำดับ (เช่น linked list) โดยใช้สองตัวชี้ที่เคลื่อนที่ด้วยความเร็วต่างกัน หากมีลูปอยู่ ตัวชี้ที่เร็วจะตามทันและพบตัวชี้ที่ช้า มันใช้พื้นที่เพิ่มเติม **O(1)**

## แนวคิด

เลื่อนตัวชี้ **slow** ไปหนึ่งขั้นตอนและตัวชี้ **fast** ไปสองขั้นตอน ในลูป ช่องว่างลดลงทีละหนึ่งในแต่ละขั้นตอน ดังนั้นจึงต้องชนกัน โดยไม่มีลูป fast จะถึงจุดสิ้นสุด

## ตัวอย่าง

```python
def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next            # +1 step
        fast = fast.next.next       # +2 steps
        if slow is fast:            # pointers met -> cycle
            return True
    return False                    # fast hit the end -> no cycle
```

## ความซับซ้อน

- **เวลา:** O(n). **พื้นที่:** O(1).

วิธี hash-set ก็ใช้ได้เช่นกันแต่ใช้พื้นที่ O(n); Floyd's ใช้พื้นที่คงที่

## เมื่อใดที่ควรใช้ / ข้อผิดพลาด

ใช้สำหรับ **การตรวจจับลูปใน linked list** การค้นหาจุดเริ่มต้นของลูป และการตรวจจับลูปในกราฟฟังก์ชันแบบ (แต่ละโหนดมีตัวสืบทอดหนึ่งตัว) ป้องกัน `fast.next` เสมอเพื่อหลีกเลี่ยง null dereferences สำหรับกราฟทั่วไป ให้ใช้ DFS กับ recursion stack แทน

## เหตุใดจึงมีความสำคัญ

การตรวจจับลูปเป็นสิ่งจำเป็นสำหรับการสำรวจที่ปลอดภัย — ลูปที่ไม่ตรวจพบหมายความว่าการวนซ้ำไม่สิ้นสุด

อัลกอริทึมของ Floyd เป็นตัวอย่างที่สวยงามของการแก้ปัญหา O(n)-space ใน O(1) space ด้วยค่าคงที่ที่ฉลาด

มันปรากฏในการสัมภาษณ์ linked list และในการตรวจจับลูปไม่สิ้นสุดใน state machines และลำดับตัวเลข