Problem link ও উৎস
- **Original source:** Classic capstone interview problem (Floyd's tortoise and hare)
- **Platform:** LeetCode —
- **Topic:** linked lists + two-pointer technique
- **Difficulty:** Easy
- **Pattern:** Slow/fast pointers (Floyd's cycle detection)
- **Basic idea inherited from:** এটা একটা cross-topic capstone — এখানে মেশে **03 linked lists** (node-এর `next` ধরে ধরে হাঁটা, কিন্তু এখানে list শেষ নাও হতে পারে) আর **02 two-pointer thinking** (একই sequence-এ দুটো আলাদা গতির আঙুল চালানো)। দুই tool জোড়া লাগলেই Floyd।
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা singly linked list দেওয়া। কখনো কখনো শেষ node `None`-এ না গিয়ে আগের কোনো node-এ ফিরে তাকায় — তখন list-এ একটা **চক্র (cycle)** তৈরি হয়, আর হাঁটতে থাকলে তুমি ঘুরতেই থাকবে, কখনো থামবে না। তোমার কাজ: শুধু বলো list-এ cycle আছে কি নেই — `True` বা `False`। (cycle কোথায় শুরু, সেটা এখানে চাওয়া হয়নি।)
```text
cycle আছে: 1 -> 2 -> 3 -> 4
^ |
+----<----+ (4 আবার 2-এ ফিরে গেছে)
cycle নেই: 1 -> 2 -> 3 -> None
```
### Input ও output {#8-example-input-and-output}
```text
Input : 3 -> 2 -> 0 -> -4, শেষ node ফিরে index 1 (value 2)-এ -> Output: True
Input : 1 -> 2, শেষ node ফিরে index 0-এ -> Output: True
Edge case 1 (খালি list): Input: None -> Output: False
Edge case 2 (একটা node, cycle নেই): Input: 1 -> None -> Output: False
Edge case 3 (একটা node নিজের দিকে): Input: 1 -> 1(self) -> Output: True
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
একটা গোল রানিং ট্র্যাকে দুজন দৌড়বিদ ভাবো — একজন ধীরে, একজন দ্বিগুণ দ্রুত। ট্র্যাক যদি বৃত্তাকার (cycle) হয়, দ্রুতজন একসময় ঘুরে এসে ধীরজনকে **ল্যাপ** করে ফেলবে — দুজন একই জায়গায় মিলবে। কিন্তু রাস্তা যদি সোজা হয়ে কোথাও শেষ হয়ে যায় (`None`), দ্রুতজন আগে প্রান্তে পৌঁছে যায়, কখনো ধরা পড়ে না।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এই problem দুটো আগের chapter-এর tool জোড়া দেয়:
- **03 linked lists** থেকে: `next` arrow ধরে হাঁটা — কিন্তু এখানে মোচড় হলো list শেষ নাও হতে পারে, তাই সাধারণ traversal আটকে যায়।
- **02 two-pointer thinking** থেকে: একই sequence-এ দুটো pointer, আলাদা গতিতে — একটা ধীর (এক ঘর), একটা দ্রুত (দুই ঘর)।
একা list-traversal cycle-এ অসীম লুপে পড়ে; একা two-pointer idea দেয় গতি-পার্থক্যের কৌশল। দুটো মিললে O(1) space-এ cycle ধরা।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic একটা **relative-speed argument**: দুটো pointer যদি একই cycle-এ থাকে আর প্রতি step-এ একটা অন্যটার চেয়ে ঠিক 1 ঘর এগিয়ে যায়, তাহলে তাদের মধ্যেকার দূরত্ব প্রতি step-এ 1 করে কমে — তাই দ্রুতটা ধীরটাকে অবশ্যই **ধরে ফেলবে** (গ্যাপ শেষে 0 হবে)। cycle না থাকলে দ্রুত pointer `None`-এ গিয়ে পড়ে, লুপ থামে। এটাই Floyd-এর গণিত।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
কোনো extra data structure লাগে না — শুধু **দুটো pointer** (`slow`, `fast`)। (একটা সহজ বিকল্প: দেখা node গুলো একটা `set`-এ রাখা, কিন্তু সেটা O(n) space; Floyd O(1) space-এ একই কাজ করে — এটাই 02 two-pointer-এর জিত।)
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
Linked list-এ আমরা শুধু `next` ধরে সামনে যেতে পারি, পিছনে না — তাই "আগে কোথায় ছিলাম" মনে রাখা কঠিন। দুটো ভিন্ন-গতির pointer এই সীমাবদ্ধতাকেই কাজে লাগায়: extra memory-তে history না রেখে, শুধু গতির পার্থক্য দিয়ে cycle ধরা পড়ে। এজন্যই two-pointer (02) linked list (04)-এর সাথে এখানে নিখুঁত খাপ খায়।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: যত node দেখি, প্রতিটার পরিচয় একটা `set`-এ রাখি; হাঁটতে হাঁটতে যদি আগে-দেখা কোনো node-এ আবার পৌঁছাই, তাহলে cycle আছে।
```text
seen = set()
while node:
if node in seen: return True
seen.add(node)
node = node.next
return False
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
সময় O(n) ঠিকই, কিন্তু এটা **O(n) extra space** নেয় — প্রতিটা node-এর reference `set`-এ জমে। Interview-র আসল চ্যালেঞ্জ O(1) space-এ cycle ধরা, কোনো extra memory ছাড়া। ঠিক এই জায়গায় two-pointer (02) আসে: history না রেখেও গতি-পার্থক্য দিয়ে একই কাজ।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **দুটো pointer ভিন্ন গতিতে চললে, cycle থাকলে তারা একসময় একই node-এ মিলবেই; cycle না থাকলে দ্রুতটা `None`-এ পড়বে।** তাই দেখা-node মনে রাখার দরকার নেই — শুধু "তারা কি মিলল?" দেখলেই হয়। এটাই O(1) space এনে দেয়।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
`slow` আর `fast` দুটোই head থেকে শুরু করো। প্রতি ধাপে `slow` এক ঘর, `fast` দুই ঘর এগোয়। যদি কখনো `slow == fast` হয় → cycle আছে (`True`)। যদি `fast` বা `fast.next` `None` হয়ে যায় → সোজা প্রান্ত পেয়ে গেছ, cycle নেই (`False`)।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "কোন node আগে দেখেছি মনে রাখব" ভাবার বদলে ভাবো "দুটো ভিন্ন-গতির আঙুল চালাই — মিললে চক্র, একজন প্রান্তে পৌঁছালে সোজা।" memory-র জায়গায় গতির পার্থক্য কাজ করে।
### ছবিতে বোঝা {#7-visual-explanation}
`1 -> 2 -> 3 -> 4 -> 2`(4 ফিরে 2-এ) — slow এক ঘর, fast দুই ঘর:
```text
শুরু: slow=1 fast=1
step1: slow=2 fast=3
step2: slow=3 fast=2 (fast ঘুরে এসেছে)
step3: slow=4 fast=4 <- slow == fast, cycle ধরা পড়ল!
cycle না থাকলে fast একসময় None-এ পড়ত আর লুপ থামত -> False
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `1 -> 2 -> 3 -> 1`(3 ফিরে 1-এ):
1. শুরু: `slow=1`, `fast=1`
2. step: `slow=2`, `fast=3`
3. step: `slow=3`, `fast=2` (`fast` `1`-এ গিয়ে আবার `2`)
4. step: `slow=1`, `fast=1`... আসলে এর আগেই: `slow=3 -> 1`, `fast=2 -> 3 -> 1`; `slow == fast == 1` → return `True`
(cycle না থাকলে কোনো এক step-এ `fast` বা `fast.next` `None` হতো, return `False`)
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def has_cycle(head):
slow = fast = head
while fast and fast.next: # fast দুই ঘর এগোবে, তাই দুটোই থাকতে হবে
slow = slow.next # ধীর: এক ঘর
fast = fast.next.next # দ্রুত: দুই ঘর
if slow is fast: # মিলে গেছে -> cycle
return True
return False # fast প্রান্তে পৌঁছেছে -> cycle নেই
# ---- helpers (test-এর জন্য) ----
def build_with_cycle(values, pos):
# pos = -1 হলে cycle নেই; নাহলে শেষ node index pos-এ ফিরে তাকায়
if not values:
return None
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]
return nodes[0]
# ---- tests ----
assert has_cycle(build_with_cycle([3, 2, 0, -4], 1)) is True # 4 -> 2
assert has_cycle(build_with_cycle([1, 2], 0)) is True # 2 -> 1
assert has_cycle(build_with_cycle([1, 2, 3], -1)) is False # সোজা list
assert has_cycle(build_with_cycle([], -1)) is False # খালি
assert has_cycle(build_with_cycle([1], -1)) is False # একক, cycle নেই
assert has_cycle(build_with_cycle([1], 0)) is True # একক, নিজের দিকে
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `slow = fast = head` — দুজনেই head থেকে শুরু।
- `while fast and fast.next` — `fast` দুই ঘর লাফায়, তাই `fast` এবং `fast.next` দুটোই থাকা চাই; এদের একটা `None` মানেই সোজা প্রান্ত।
- `slow = slow.next` — ধীর pointer এক ঘর।
- `fast = fast.next.next` — দ্রুত pointer দুই ঘর।
- `if slow is fast` — একই node object হলে (`is`, value-সমতা না) cycle নিশ্চিত; return `True`।
- `return False` — লুপ স্বাভাবিকভাবে শেষ মানে `fast` `None`-এ পৌঁছেছে, কোনো cycle নেই।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`[3,2,0,-4]` (4 ফিরে 2-এ): `slow`/`fast` কয়েক ধাপে cycle-এর ভেতর একই node-এ মেলে → `True` — assert pass। `[1,2,3]` সোজা list-এ `fast` শেষে `None`-এ পড়ে → `False`। খালি ও একক-node case-ও সঠিক; একক node নিজের দিকে তাকালে এক ধাপেই `slow is fast` → `True`। শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(n)** — cycle না থাকলে `fast` ~n/2 ধাপে প্রান্তে; cycle থাকলে দুজনে cycle-দৈর্ঘ্যের মধ্যে মেলে — মোট রৈখিক।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(1)** — শুধু দুটো pointer; দেখা node মনে রাখার set লাগে না (এটাই brute force-এর উপর Floyd-এর জিত)।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- `while` শর্তে শুধু `fast` দেখা (`fast.next` বাদ) — তখন `fast.next.next`-এ `None.next` crash করবে।
- `slow == fast` (value সমতা) লেখা `slow is fast`-এর বদলে — ভিন্ন node-এর value এক হলে ভুল `True` দিতে পারে; identity (`is`) চাই।
- খালি list / একক node আলাদা করে না ভাবা — যদিও `while` শর্ত এমনিতেই এদের সামলায়, মুখে edge case বলা rubric-এ গোনে।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: linked list traversal (03-এর [../../03-linked-list/](../../03-linked-list/README.md)) + একই sequence-এ দুই-গতির pointer চালানো (02 two-pointer, [../../02-arrays-and-strings/](../../02-arrays-and-strings/README.md))। "find the middle of a list" (slow/fast)-ও ঠিক একই কৌশলের ভাই।
### পরের অনুশীলন {#22-similar-harder-problems}
- Linked List Cycle II (cycle কোথায় শুরু, সেই node ফেরত দাও) —