Fast and Slow Pointers for Cycle Entry
آمادگی مصاحبهٔ الگوریتمی با Python
- In 75 minutes, introduce a singly linked node through val and next references, None termination, and object identity rather than value equality.
- Recognize a single-successor sequence that may revisit an earlier node; reject direct use on general branching graphs.
- Compare repeated rescanning and a visited-node set with a constant-space fast/slow approach for Linked List Cycle II.
- Independently predict a meeting on a small drawn list, then implement safe one-step and two-step movement in Python.
- Explain why relative movement guarantees a meeting inside a cycle; derive the reset-and-walk rule using distances modulo cycle length.
- Implement cycle-entry detection with O(n) time and O(1) auxiliary space without modifying the list.
- Test an empty list, a terminating singleton, a self-loop, entry at the head, and equal values in distinct nodes; diagnose comparing values and dereferencing None.
هویت node و محدودیت حافظه
**قرارداد مسئله**
خروجی: خود node ورودی چرخه؛ بدون چرخه: `None`
بدون تغییر لیست؛ حافظهٔ کمکی \(O(1)\)
**مقدار یکسان، هویت متفاوت**
`head → A → B → None`
`A.val = B.val = 7`، ولی `A is B` نادرست است؛ چرخه نداریم.
اشارهگر یک reference است، نه کپیِ شیء.
**Brute Force با بازپیمایی محدود**
پیش از پذیرش `current`، از `head` فقط به تعداد nodeهای قبلی جلو برو؛ هویت هرکدام را با `current` بسنج.
اولین تکرار: خود `current`، ورودی چرخه است.
زمان بدترین حالت: \(O(n^2)\)؛ حافظهٔ کمکی: \(O(1)\)
**visited set از هویتها**
اولین هویت تکراری، نه اولین مقدار تکراری
زمان موردانتظار: \(O(n)\)؛ حافظهٔ کمکی: \(O(n)\)
این حافظهٔ خطی باید حذف شود.
**نشانهٔ Fast/Slow Pointers**
از هر node فقط یک ادامه داریم.
در graph شاخهدار، چند مسیر ممکن است؛ این روش مستقیماً جواب نمیدهد.
برخورد، لزوماً ورودی نیست
```svg
<svg viewBox="0 0 800 600" xmlns="http://www.w3.org/2000/svg"><defs><marker id="arr" markerWidth="8" markerHeight="8" refX="7" refY="4" orient="auto"><path class="tm-arrow" d="M0 0 L8 4 L0 8 Z"/></marker></defs><path class="tm-line" d="M106 105 H204 M256 105 H354 M406 105 H504 M556 105 H654 M680 131 V175 H380 V131" fill="none" marker-end="url(#arr)"/><circle class="tm-soft" cx="80" cy="105" r="26"/><circle class="tm-surface" cx="230" cy="105" r="26"/><circle class="tm-green" cx="380" cy="105" r="26"/><circle class="tm-surface" cx="530" cy="105" r="26"/><circle class="tm-surface" cx="680" cy="105" r="26"/><g font-size="22" text-anchor="middle"><text class="tm-text" x="80" y="112">A</text><text class="tm-text" x="230" y="112">B</text><text class="tm-text" x="380" y="112">C</text><text class="tm-text" x="530" y="112">D</text><text class="tm-text" x="680" y="112">E</text></g><text class="tm-text" x="80" y="48" text-anchor="middle" font-size="18">slow / fast</text><text class="tm-text-green" x="380" y="48" text-anchor="middle" font-size="18" direction="rtl">ورودی</text><text class="tm-text-accent" x="530" y="48" text-anchor="middle" font-size="18" direction="rtl">برخورد</text><text class="tm-muted" x="400" y="220" text-anchor="middle" font-size="18" direction="rtl">برابری اولیه برخورد نیست؛ اول حرکت، بعد سنجش هویت</text><text class="tm-text-accent" x="400" y="263" text-anchor="middle" font-size="19" direction="rtl">دور اول: slow: A → B | fast: A → B → C</text><text class="tm-text-accent" x="400" y="303" text-anchor="middle" font-size="19" direction="rtl">دور دوم: slow: B → C | fast: C → D → E</text><text class="tm-text-accent" x="400" y="343" text-anchor="middle" font-size="19" direction="rtl">دور سوم: slow: C → D | fast: E → C → D</text><rect class="tm-soft" x="75" y="375" width="650" height="140" rx="12"/><text class="tm-text" x="95" y="405" font-size="17" font-family="monospace">while fast is not None and fast.next is not None:</text><text class="tm-text" x="115" y="435" font-size="17" font-family="monospace">slow = slow.next</text><text class="tm-text" x="115" y="465" font-size="17" font-family="monospace">fast = fast.next.next</text><text class="tm-text" x="115" y="495" font-size="17" font-family="monospace">if slow is fast:</text><text class="tm-text-accent tm-enter" x="400" y="550" text-anchor="middle" font-size="19" direction="rtl">داخل چرخه: هر دور یک قدم پیشروی نسبی</text><text class="tm-text" x="400" y="580" text-anchor="middle" font-size="18" direction="rtl">حداکثر بهاندازهٔ طول چرخه تا برخورد</text></svg>
```
چرا بازنشانی به ورودی میرسد؟
پس از برخورد: بازنشانی slow به head؛ سپس حرکت هر دو با سرعت یکسان.
**شروع دوباره**
\[ (\mathrm{slow},\mathrm{fast})=(A,D) \]
**دو قدم تا ورودی**
\[ (A,D)\longrightarrow(B,E)\longrightarrow(C,C) \]
خروجی: \(C\)
**فاصلهٔ طیشده توسط slow**
\[ d_{\mathrm{slow}}=a+xL+b,\qquad 0\le b<L \]
\(a\): فاصلهٔ head تا ورودی؛ \(L\): طول چرخه؛ \(b\): فاصلهٔ رو به جلو از ورودی تا برخورد؛ \(x\): تعداد دورهای کامل slow
**فاصلهٔ طیشده توسط fast**
\[ d_{\mathrm{fast}}=a+yL+b \]
\(y\): تعداد دورهای کامل fast
**سرعت دوبرابر تا برخورد**
\[ d_{\mathrm{fast}}=2d_{\mathrm{slow}}\quad\Longrightarrow\quad a+yL+b=2(a+xL+b) \]
**حذف بخشهای مشترک**
\[ a+yL+b=2a+2xL+2b\quad\Longrightarrow\quad a=(y-2x)L-b \]
**رابطهٔ کلیدی**
\[ a+b=(y-2x)L\quad\Longrightarrow\quad a+b\equiv0\pmod L \]
**بررسی مثال**
\[ \begin{gathered}a=2,\quad L=3,\quad b=1\\d_{\mathrm{slow}}=3,\quad d_{\mathrm{fast}}=6\\a+b=2+1=3=L\end{gathered} \]
**رسیدن همزمان به ورودی**
\[ \begin{gathered}(b+a)\bmod L=0\\\mathrm{head}\xrightarrow{\ a\ }\mathrm{entry}\qquad\mathrm{meeting}\xrightarrow{\ a\ }\mathrm{entry}\end{gathered} \]
زودتر یکی نمیشوند: تا پیش از ورودی، یکی بیرون چرخه و دیگری داخل آن است.
**اگر ورودی همان head باشد**
\[ a=0\quad\Longrightarrow\quad b\equiv0\pmod L\quad\Longrightarrow\quad b=0 \]
قدم اضافه لازم نیست. محاسبهٔ \(L\) فقط برای اثبات است، نه اجرای الگوریتم.
پیادهسازی دو مرحله در Python
**برگرداندن خود node، نه مقدار آن**
```python
def detectCycle(head):
slow = fast = head
while fast is not None and fast.next is not None:
slow = slow.next
fast = fast.next.next
if slow is fast:
slow = head
while slow is not fast:
slow = slow.next
fast = fast.next
return slow
return None
```
**اجرای دستی مثال A تا E**
| وضعیت | `slow` | `fast` |
|---|---|---|
| برخورد در حلقهٔ اول | `D` | `D` |
| بازنشانی | `A` | `D` |
| حرکت مشترک اول | `B` | `E` |
| حرکت مشترک بعدی | `C` | `C` |
خروجی: خود `C`؛ مقایسهٔ هویت با `is`، نه مقایسهٔ مقدار.
**تورفتگی مهم است:** `return slow` بعد از حلقهٔ داخلی و داخل `if` است؛ `return None` بیرون حلقهٔ اول است.
هیچ `val` یا `next` تغییر نمیکند؛ فقط referenceهای محلی جابهجا میشوند.
تستهای مرزی و هزینهٔ اجرا
**مسیرهای بدون چرخه**
`head is None` ← خروجی `None`
تکnode با `next is None` ← خروجی `None`
**چرخههای کوچک**
تکnode با `next` به خودش: برخورد و خروجی همان node.
`A → B → A`
`(slow, fast): (A, A) → (B, A) → (A, A)`
پس از بازنشانی: خروجی `A`.
**هویت، نه مقدار**
`A → B → None` با `A.val == B.val == 7`
دو شیء جدا؛ خروجی `None`، نه چرخه.
آزمون خروجی: `result is expected_node`، نه فقط مقایسهٔ `val`.
**هر دو بخش شرط لازماند**
شرط امن: `fast is not None and fast.next is not None`
فقط `fast.next`: خواندن `next` از `None` در ورودی خالی.
فقط `fast`: خواندن `next` از `None` در حرکت دوقدمیِ تکnode بدون چرخه.
**شمارش قدمها**
\(n\): تعداد nodeهای متمایز قابلدسترسی؛ \(L\): طول چرخه.
بدون چرخه: \(O(n)\).
با چرخه: تا برخورد \(\le a+L\) قدمِ `slow`؛ پس از بازنشانی \(a\) قدم.
\(n=a+L\)، پس \(2a+L\le 2n\).
زمان \(O(n)\)، حافظهٔ کمکی \(O(1)\)؛ بدون `set` و بدون تغییر لیست.
**از صفر بنویس و توضیح بده**
چرا این الگو مناسب است؟
چرا برخورد لزوماً ورودی نیست؟
چرا بازنشانی به `head` جواب میدهد؟
Back to course