Problem link ও উৎস
- **Original source:** Classic linked list exercise (Floyd's cycle detection)
- **Platform:** LeetCode —
- **Topic:** linked list
- **Difficulty:** Easy
- **Pattern:** slow/fast pointers (Floyd's tortoise and hare)
- **Basic idea inherited from:** traversal, কিন্তু দুই speed-এ একসাথে চালানো
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা linked list দেওয়া। এতে কি কোনো **cycle** (চক্র) আছে? মানে — হাঁটতে হাঁটতে কি কখনো আগের কোনো node-এ ফিরে আসবে আর চিরকাল ঘুরতে থাকবে? `True`/`False` return করো।
```text
cycle আছে: 1 -> 2 -> 3 -> 4
^ |
└─────────┘ (4 আবার 2-তে ফেরে)
cycle নেই: 1 -> 2 -> 3 -> 4 -> None
```
### Input ও output {#8-example-input-and-output}
```text
Input : 3 -> 2 -> 0 -> -4 , শেষ node আবার 2-তে যুক্ত -> Output: True
Input : 1 -> 2 , শেষ node আবার 1-তে যুক্ত -> Output: True
Input : 1 -> None -> Output: False
Input : None -> Output: False
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
গোল রানিং ট্র্যাকে দুজন দৌড়বিদ একসাথে শুরু করল — একজন আস্তে, একজন দ্বিগুণ জোরে। ট্র্যাক যদি গোল (cycle) হয়, দ্রুতজন একসময় পিছন থেকে ধীরজনকে **lap** দিয়ে ধরে ফেলবে। ট্র্যাক যদি সোজা হয়ে শেষ হয়ে যায় (None), তারা আর কখনো মিলবে না।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
ভিত্তি হলো সাধারণ **traversal** — list ধরে হাঁটা। নতুনত্ব: একটার বদলে **দুটো** pointer একসাথে হাঁটাই, ভিন্ন গতিতে। এই "দুই speed" idea-টাই পরে middle খোঁজা (problem 4) আর cycle-start খোঁজা (problem 11)-তে ফিরে আসবে।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো অঙ্ক: একটা বদ্ধ বৃত্তে যদি একজন প্রতি step-এ ১ ঘর আর আরেকজন ২ ঘর এগোয়, তাহলে দ্রুতজন ধীরজনের সাথে **নিশ্চিতভাবে** একসময় মিলবে — কারণ প্রতি step-এ তাদের মধ্যে দূরত্ব ঠিক ১ করে কমে, তাই কখনো ০ হবেই (একে অপরকে "টপকে" যেতে পারে না)। cycle না থাকলে দ্রুতজন আগে `None`-এ পৌঁছে যায়।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
দুই রকম সমাধান:
- সহজ: একটা **hash set**-এ দেখা node গুলো রাখো; আবার এলে cycle।
- সেরা: **দুটো pointer** (slow, fast) — কোনো extra structure ছাড়াই, O(1) space।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
hash set লাগলে O(n) extra memory। কিন্তু linked list-এ আমরা একই node-এ **দুই গতিতে** হাঁটতে পারি — তাই দুটো pointer-ই যথেষ্ট। cycle-এর ভেতরে ঢুকলে fast পিছন থেকে slow-কে ধরে ফেলে; এটা O(1) space-এ cycle ধরার নিখুঁত উপায়।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রতিটা node visit করার সময় তাকে একটা **set**-এ রাখো। নতুন node যদি আগে থেকেই set-এ থাকে → cycle। `None`-এ পৌঁছালে → cycle নেই।
```text
seen = {}
3 দেখলাম -> seen={3}
2 দেখলাম -> seen={3,2}
0 দেখলাম -> seen={3,2,0}
-4 দেখলাম -> seen={3,2,0,-4}
আবার 2 -> 2 already seen -> True
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
সময় O(n) ঠিকই, কিন্তু **space O(n)** — সব node set-এ রাখতে হয়। বড় list-এ এটা অপচয়। দুই-pointer পদ্ধতি একই কাজ **O(1) space**-এ করে।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
cycle থাকলে দ্রুত-pointer ধীর-pointer-কে **ভেতরের চক্রে** একসময় ধরবেই; cycle না থাকলে দ্রুত-pointer তার আগে list-এর শেষ (`None`) ছুঁয়ে ফেলবে। তাই "fast None ছুঁলো না slow-কে ধরল" — এই দুটোর একটা ঘটবেই।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
`slow` আর `fast` দুটোকেই head থেকে শুরু করো। প্রতি step-এ `slow` ১ ঘর, `fast` ২ ঘর এগোও। যদি কখনো `slow is fast` → cycle আছে। যদি `fast` (বা `fast.next`) `None` হয়ে যায় → cycle নেই।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** cycle ধরতে "কোথায় কোথায় গেছি" মনে রাখার (set) দরকার নেই — শুধু **দুই গতির দুটো pointer** ছাড়ো; cycle থাকলে দ্রুতজন ধীরজনকে ধরে ফেলবেই। স্মৃতির বদলে গতি।
### ছবিতে বোঝা {#7-visual-explanation}
`slow` ১ ঘর, `fast` ২ ঘর। `1→2→3→4` এবং `4.next=2` (চক্র: 2→3→4→2):
```text
শুরু: slow=1, fast=1
step 1: slow=2, fast=3
step 2: slow=3, fast=2 (fast: 3->4->2)
step 3: slow=4, fast=4 ← slow == fast → cycle! True
cycle নেই (1->2->3->None):
step 1: slow=2, fast=3
পরের guard: fast=3 কিন্তু fast.next=None; loop চলে না → False
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
`1 -> 2 -> 3 -> 4`, আর `4.next = 2` (cycle):
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` → return `True`
## কোড ও ব্যাখ্যা {#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 None ছুঁলো → cycle নেই
# ---- helper: values + cycle position (-1 = no cycle) দিয়ে list বানাও ----
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[0] if nodes else None
# ---- tests ----
assert has_cycle(build_with_cycle([3, 2, 0, -4], pos=1)) is True
assert has_cycle(build_with_cycle([1, 2], pos=0)) is True
assert has_cycle(build_with_cycle([1], pos=-1)) is False
assert has_cycle(build_with_cycle([], pos=-1)) is False
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `slow = fast = head` — দুজনেই head থেকে শুরু।
- `while fast and fast.next:` — `fast` দুই ঘর লাফায়, তাই `fast` ও `fast.next` দুটোই থাকতে হবে; নাহলে list শেষ → cycle নেই।
- `slow = slow.next` — ধীরজন ১ ঘর।
- `fast = fast.next.next` — দ্রুতজন ২ ঘর।
- `if slow is fast:` — একই node-এ মিলেছে (`is` = একই object, value নয়) → cycle।
- `return False` — loop স্বাভাবিকভাবে শেষ মানে `fast` None ছুঁয়েছে → cycle নেই।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`[3,2,0,-4]` pos=1 → 4 নম্বর node 2-তে ফেরে → `True`। `[1,2]` pos=0 → `True`। একক node, cycle নেই → `False`। খালি → `False`। সব assert pass → `সব test pass!`।
### JavaScript ও test cases {#25-javascript-solution-with-test-cases}
```javascript
const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };
class ListNode {
constructor(val = 0, next = null) { this.val = val; this.next = next; }
}
// ---- values + cycle position (-1 = no cycle) দিয়ে list বানাও ----
const buildWithCycle = (values, pos = -1) => {
const nodes = values.map(v => new ListNode(v));
for (let i = 0; i < nodes.length - 1; i++) nodes[i].next = nodes[i + 1];
if (pos !== -1 && nodes.length) nodes[nodes.length - 1].next = nodes[pos]; // cycle জোড়ো
return nodes.length ? nodes[0] : null;
};
function hasCycle(head) {
let slow = head, fast = head;
while (fast && fast.next) { // fast দুই ঘর এগোবে, তাই দুটোই থাকা চাই
slow = slow.next; // ১ ঘর
fast = fast.next.next; // ২ ঘর
if (slow === fast) return true; // দেখা হয়ে গেল -> cycle
}
return false; // fast None ছুঁলো -> cycle নেই
}
// ---- test cases ----
assert(hasCycle(buildWithCycle([3, 2, 0, -4], 1)) === true, "cycle@1");
assert(hasCycle(buildWithCycle([1, 2], 0)) === true, "cycle@0");
assert(hasCycle(buildWithCycle([1], -1)) === false, "single no cycle");
assert(hasCycle(buildWithCycle([], -1)) === false, "empty");
console.log("সব JS test pass!");
```
> **JS টীকা:** node-পরিচয় তুলনায় `===` ব্যবহার করো (`slow === fast`) — এটা reference equality, মানে "একই object কি না", value নয়; তাই দুটো ভিন্ন node-এর val সমান হলেও ভুল `true` আসবে না। `buildWithCycle` helper-এ একটা node-কে অন্য node-এ `next` দিয়ে জুড়ে ইচ্ছাকৃত cycle বানাই — তা নাহলে `node`-এ cycle test করাই যেত না। `while (fast && fast.next)` দুটোই check করে যাতে `fast.next.next`-এ crash না হয়।
### TypeScript ও test cases {#26-typescript-solution-with-test-cases}
```typescript
interface ListNode { val: number; next: ListNode | null }
const buildWithCycle = (values: number[], pos = -1): ListNode | null => {
const nodes: ListNode[] = values.map(v => ({ val: v, next: null }));
for (let i = 0; i < nodes.length - 1; i++) nodes[i].next = nodes[i + 1];
if (pos !== -1 && nodes.length) nodes[nodes.length - 1].next = nodes[pos];
return nodes.length ? nodes[0] : null;
};
function hasCycle(head: ListNode | null): boolean {
let slow: ListNode | null = head;
let fast: ListNode | null = head;
while (fast && fast.next) {
slow = slow!.next; // slow fast-এর পিছনে, তাই fast থাকলে slow-ও আছে
fast = fast.next.next;
if (slow === fast) return true;
}
return false;
}
function expect