الگوی اشاره‌گر کند و تند
اشاره‌گر کند و تند (Floyd): تشخیص حلقه در لیست پیوندی، پیدا کردن وسط و شروع حلقه — با سرعت دوبرابر
ایده الگو
دو اشاره‌گر با سرعت متفاوت: تند ۲ قدم، کند ۱ قدم. اگر حلقه وجود داشته باشد، تند دوباره به کند می‌رسد (مثل دو دونده در پیست!).
کاربرد ۱: تشخیص حلقه
در لیست پیوندی یا آرایه‌ای که هر خانه به خانه‌ای دیگر اشاره می‌کند:
- اگر تند به None رسید ← بدون حلقه
- اگر تند == کند شد ← حلقه هست!
چرا قطعاً می‌رسند؟ در هر گام فاصله‌شان ۱ کم می‌شود (تند ۲ جلو، کند ۱) — مثل شکار حتمی.
کاربرد ۲: پیدا کردن شروع حلقه
بعد از برخورد، یکی را به ابتدا برگردانید و هر دو را با سرعت ۱ حرکت دهید — نقطه برخورد دوم = شروع حلقه! (ریاضیات زیبا پشت آن است: فاصله از ابتدا تا شروع = فاصله از نقطه برخورد تا شروع)
کاربرد ۳: وسط لیست
وقتی تند به انتها رسید، کند دقیقاً وسط است — یک پیمایش، بدون دانستن طول!
کاربرد ۴: آرایه‌های دوری و «آشفته»
مسئله «Find Duplicate Number»: آرایه‌ای که مقدارها به عنوان «اشاره‌گر» عمل می‌کنند — کند/تند حلقه را پیدا می‌کند و شروع حلقه = عدد تکراری!
| مسئله | راه‌حل کند/تند |
|---|---|
| حلقه در لیست پیوندی | برخورد = حلقه |
| شروع حلقه | برخورد + بازگشت به ابتدا |
| وسط لیست | تند تمام ← کند وسط |
| عدد تکراری (بدون تغییر آرایه) | آرایه = گراف تابعی |
| خوش‌بختی عدد (Happy Number) | دنباله مربع ارقام = حلقه‌یاب |
جمع‌بندی
- تند ۲ قدم، کند ۱ قدم — در حلقه قطعاً می‌رسند
- شروع حلقه: برخورد + هر دو با سرعت ۱
- وسط لیست در یک پیمایش
- O(n) زمان + O(1) حافظه — قهرمان فضا
این مبحث بخشی از دوره آموزش کامل الگوریتم‌ها است.