Problem link ও উৎস
- **Original source:** Classic linked list exercise (Floyd's cycle detection, phase 2)
- **Platform:** LeetCode —
- **Topic:** linked list
- **Difficulty:** Medium
- **Pattern:** Floyd's phase 2 (slow/fast meet, তারপর head থেকে আবার)
- **Basic idea inherited from:** cycle detection (problem 3) + distance algebra
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা linked list-এ যদি cycle (চক্র) থাকে, তাহলে সেই চক্রটা **কোন node থেকে শুরু** হয়েছে সেই node-টা return করো। cycle না থাকলে `None` return করো।
```text
1 -> 2 -> 3 -> 4
^ |
└─────────┘ (4 আবার 2-তে ফেরে)
cycle শুরু = node 2
```
### Input ও output {#8-example-input-and-output}
```text
Input : 3 -> 2 -> 0 -> -4 , শেষ node 2-তে ফেরে -> Output: node 2 (index 1)
Input : 1 -> 2 , শেষ node 1-তে ফেরে -> Output: node 1 (index 0)
Input : 1 -> 2 -> 3 (cycle নেই) -> Output: None
Input : 1 (cycle নেই) -> Output: None
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
গোল ট্র্যাকে দুজন দৌড়বিদ — একজন দ্বিগুণ জোরে — কোথাও একটা lap-এ মিলল (phase 1)। এবার একজন আবার শুরুর গেটে ফিরে গিয়ে দুজনে **একই** গতিতে হাঁটল; অঙ্কের নিয়মে তারা ঠিক সেই জায়গায় মিলবে যেখানে সোজা রাস্তা ট্র্যাকের গোল অংশে ঢুকেছে — অর্থাৎ চক্রের প্রবেশমুখ।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এটা সরাসরি problem 3 ([[003-linked-list-cycle.md](003-linked-list-cycle.md)](003-linked-list-cycle.md))-এর উপর দাঁড়িয়ে। সেখানে শুধু "cycle আছে কি না" ধরা হয়েছিল slow/fast দিয়ে। এখানে এক ধাপ এগিয়ে — **কোথায় শুরু** সেটা বের করা। নতুন উপাদান একটা সুন্দর **distance algebra** (দূরত্বের অঙ্ক), যা phase 2-তে কাজে লাগে।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
ধরা যাক head থেকে cycle-শুরু পর্যন্ত দূরত্ব `a`, cycle-শুরু থেকে দেখা-হওয়ার বিন্দু পর্যন্ত `b`, আর চক্রের দৈর্ঘ্য `c`। দেখা হওয়ার সময় slow গেছে `a + b`, fast গেছে `a + b + k·c` (k বার চক্র ঘুরে)। fast দ্বিগুণ গতির, তাই `2(a + b) = a + b + k·c`, অর্থাৎ `a + b = k·c`, মানে `a = k·c − b = (k−1)·c + (c − b)`। ফলাফল: দেখা-বিন্দু থেকে আর head থেকে — দুজন একই গতিতে হাঁটলে তারা ঠিক **cycle-শুরুতে** মিলবে।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
কোনো extra structure নয় — শুধু **দুটো pointer**। প্রথম পর্বে `slow`/`fast` দিয়ে দেখা-বিন্দু খুঁজি; দ্বিতীয় পর্বে একটাকে head-এ ফিরিয়ে দুজনকে এক গতিতে হাঁটাই। O(1) space।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
cycle-শুরু খুঁজতে hash set-এ সব node রাখলে O(n) memory লাগত। কিন্তু উপরের distance algebra বলছে শুধু দুটো pointer-এর গতি নিয়ন্ত্রণ করেই উত্তর পাওয়া যায়। linked list-এ একই node-এ দুই গতিতে হাঁটা যায় বলেই এই অঙ্ক খাটে — তাই O(1) space-এই কাজ হয়।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
সরল চিন্তা: হাঁটতে হাঁটতে প্রতিটা node একটা **set**-এ রাখো। যেই প্রথম node আবার set-এ পাওয়া যাবে, সেটাই cycle-শুরু — সেটা return করো। `None`-এ পৌঁছালে cycle নেই।
```text
seen = {}
3 দেখলাম -> {3}
2 দেখলাম -> {3,2}
0 দেখলাম -> {3,2,0}
-4 দেখলাম -> {3,2,0,-4}
আবার 2 -> 2 already seen -> cycle শুরু = node 2
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
সময় O(n) ঠিকই, কিন্তু **space O(n)** — প্রতিটা node set-এ রাখতে হয়। Floyd-এর দুই-pointer পদ্ধতি একই উত্তর **O(1) space**-এ দেয়, কোনো node মনে না রেখেই — শুধু গতির অঙ্কে।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: phase 1-এ দেখা-হওয়ার বিন্দু থেকে আর head থেকে — এই দুই বিন্দু cycle-শুরু থেকে **সমান দূরত্বে** (mod চক্র-দৈর্ঘ্য)। তাই দুজনকে এক গতিতে হাঁটালে তারা ঠিক প্রবেশমুখে মিলবে।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
প্রথমে problem 3-এর মতো slow/fast চালাও; `slow is fast` হলে cycle আছে, ওই বিন্দু ধরে রাখো। যদি fast `None` ছোঁয় — cycle নেই, `None`। cycle থাকলে একটা pointer head-এ ফিরিয়ে দাও, তারপর দুজনকে **এক ঘর করে** একসাথে এগোও; যেখানে মিলবে, সেটাই cycle-শুরু।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "কোথায় কোথায় গেছি মনে রাখব" (set) না ভেবে ভাবো — "দেখা হয়ে গেলে একজনকে শুরুতে ফেরত পাঠাই; এবার দুজনে সমান কদমে হাঁটলে অঙ্ক নিজেই প্রবেশমুখে মিলিয়ে দেবে।" স্মৃতির বদলে দূরত্বের সমীকরণ।
### ছবিতে বোঝা {#7-visual-explanation}
দুই পর্ব। `1->2->3->4`, `4` ফেরে `2`-তে (cycle শুরু = 2):
```text
phase 1 (slow 1 ঘর, fast 2 ঘর — দেখা হওয়া পর্যন্ত):
slow=1, fast=1
slow=2, fast=3
slow=3, fast=2 (fast: 3->4->2)
slow=4, fast=4 ← দেখা! meeting = node 4
phase 2 (একটা head-এ, দুজনে 1 ঘর করে):
ptr=1 , slow=4
ptr=2 , slow=2 ← মিলল! cycle শুরু = node 2
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
`1 -> 2 -> 3 -> 4`, `4.next = 2` (cycle শুরু = node 2):
1. phase 1: `slow=1, fast=1`
2. `slow=2, fast=3`
3. `slow=3, fast=2` (fast: 3→4→2)
4. `slow=4, fast=4` → `slow is fast` → দেখা-বিন্দু = node 4
5. phase 2: `ptr=head=1`, `slow=4`
6. `ptr != slow` → `ptr=2`, `slow=2` (4→2)
7. `ptr is slow` (node 2) → return node 2
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def detect_cycle(head):
slow = fast = head
while fast and fast.next: # phase 1: দেখা-বিন্দু খোঁজা
slow = slow.next # 1 ঘর
fast = fast.next.next # 2 ঘর
if slow is fast: # দেখা হয়ে গেল
ptr = head # phase 2: একজন head-এ
while ptr is not slow: # দুজনে এক ঘর করে
ptr = ptr.next
slow = slow.next
return ptr # মিলন-বিন্দু = cycle শুরু
return None # fast None ছুঁলো → cycle নেই
# ---- helper: cycle-সহ list বানাও, সব node-এর তালিকা ফেরাও ----
def build_with_cycle(values, pos=-1):
nodes = [ListNode(v) for v in values]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i + 1]
if pos != -1:
nodes[-1].next = nodes[pos] # শেষ node-কে pos-এ জুড়ে cycle
return nodes
# ---- tests (identity দিয়ে যাচাই, value নয়) ----
nodes = build_with_cycle([3, 2, 0, -4], pos=1)
assert detect_cycle(nodes[0]) is nodes[1] # cycle শুরু = index 1
nodes = build_with_cycle([1, 2], pos=0)
assert detect_cycle(nodes[0]) is nodes[0] # cycle শুরু = index 0
nodes = build_with_cycle([1, 2, 3], pos=-1)
assert detect_cycle(nodes[0]) is None # cycle নেই
nodes = build_with_cycle([1], pos=-1)
assert detect_cycle(nodes[0]) is None # একক node, cycle নেই
assert detect_cycle(None) is None # খালি
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `slow = fast = head` — দুজনেই head থেকে শুরু (phase 1)।
- `while fast and fast.next:` — fast দুই ঘর লাফায়, তাই দুটোই থাকা চাই।
- `slow = slow.next` / `fast = fast.next.next` — ধীর ১ ঘর, দ্রুত ২ ঘর।
- `if slow is fast:` — দেখা হয়ে গেল (`is` = একই object); cycle নিশ্চিত।
- `ptr = head` — phase 2 শুরু: একটা pointer head-এ ফিরিয়ে দাও।
- `while ptr is not slow:` — দুজনকে **এক ঘর করে** একসাথে এগোও।
- `return ptr` — যেখানে মিলল, সেটাই cycle-এর প্রবেশমুখ।
- `return None` — loop স্বাভাবিকভাবে শেষ মানে fast None ছুঁয়েছে → cycle নেই।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`[3,2,0,-4]` pos=1: phase 1-এ দেখা হয়, phase 2-তে head ও মিলন-বিন্দু এক গতিতে এগিয়ে index 1-এ মেলে → `nodes[1]`। `[1,2]` pos=0 → `nodes[0]`। cycle না থাকলে fast None ছোঁয় → `None`। একক node ও খালি → `None`। সব assert pass → `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(n)** — phase 1-এ দেখা হতে রৈখিক ধাপ; phase 2-তে head থেকে প্রবেশমুখ পর্যন্ত আরও রৈখিক — মোট O(n)।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(1)** — শুধু কয়েকটা pointer; hash set-এর O(n) লাগে না।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- phase 2-তে দুজনকেই দ্বিগুণ গতিতে চালানো — দুজনেই **এক ঘর** করে এগোতে হবে।
- দেখা-বিন্দু পাওয়ার পর সেখান থেকেই দুজনকে চালানো (একজনকে head-এ ফেরত না পাঠানো)।
- `slow == fast` (value তুলনা) লেখা `slow is fast`-এর বদলে — ভিন্ন node-এর value সমান হলে ভুল হতে পারে।
- `while fast` শর্তে `fast.next` বাদ দেওয়া — `fast.next.next`-এ crash।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: problem 3 ([[003-linked-list-cycle.md](003-linked-list-cycle.md)](003-linked-list-cycle.md))-এর slow/fast cycle detection; তার উপর distance algebra বসিয়ে cycle-শুরু বের করা। দুই-speed চিন্তার ছবি [../visual-explanation.md](../visual-explanation.md)-এর "tortoise–hare" frame-এ।
### পরের অনুশীলন {#22-similar-harder-problems}
- Linked List Cycle (শুধু আছে কি না) —