Problem link ও উৎস
- **Original source:** Classic linked list exercise
- **Platform:** LeetCode —
- **Topic:** linked list
- **Difficulty:** Easy
- **Pattern:** slow/fast pointers
- **Basic idea inherited from:** cycle-check-এর skeleton (problem 3-এর slow/fast)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা singly linked list দেওয়া। তোমাকে এর **মাঝের** node-টা বের করতে হবে আর সেখান থেকে বাকি list return করতে হবে। list-এর দৈর্ঘ্য জোড় হলে দুটো মাঝ থাকে — তখন **দ্বিতীয়টা** নাও।
```text
বিজোড় (5টা): 1 -> 2 -> 3 -> 4 -> 5 মাঝ = 3
জোড় (6টা): 1 -> 2 -> 3 -> 4 -> 5 -> 6 মাঝ = 4 (দ্বিতীয়টা)
```
### Input ও output {#8-example-input-and-output}
```text
Input : 1 -> 2 -> 3 -> 4 -> 5 -> Output: 3 -> 4 -> 5 (head = node 3)
Input : 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> Output: 4 -> 5 -> 6 (দ্বিতীয় মাঝ)
Edge 1 (একটা node): 1 -> Output: 1
Edge 2 (দুটো node): 1 -> 2 -> Output: 2 (দ্বিতীয়টা)
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
দুই বন্ধু একসাথে একটা লম্বা করিডোরের শুরু থেকে হাঁটা শুরু করল। একজন স্বাভাবিক গতিতে, আরেকজন ঠিক দ্বিগুণ জোরে। দ্রুতজন যখন করিডোরের শেষ দেয়ালে পৌঁছবে, ধীরজন তখন ঠিক **মাঝখানে** দাঁড়িয়ে থাকবে — মাপজোক ছাড়াই।
## ভিত্তির ধারণা {#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))-এর **slow/fast skeleton**-এর উপর দাঁড়িয়ে। সেখানে আমরা শিখেছি দুটো pointer ভিন্ন গতিতে চালানো। এখানে cycle ধরা নয় — বরং সেই একই দুই-গতির খেলা দিয়ে এক পাসে মাঝ খুঁজে ফেলা। skeleton একই, শুধু লক্ষ্য আলাদা।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো অঙ্ক একটা সরল অনুপাত: `fast` যখন `slow`-এর **দ্বিগুণ** গতিতে এগোয়, তখন `fast` যখন শেষ ছুঁয়েছে, `slow` ঠিক **অর্ধেক** পথ গেছে। অর্ধেক পথ মানেই মাঝ। গণিতে — `fast` ২k ঘর গেলে `slow` k ঘর; `fast` শেষে (২k = n) মানে slow = n/2 = মাঝ।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
কোনো extra data structure লাগে না — শুধু **দুটো pointer** (`slow`, `fast`)। O(1) extra space-এই কাজ হয়ে যায়।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
Linked list-এ আমরা index করে সরাসরি মাঝে লাফ দিতে পারি না (length আগে থেকে জানা নেই)। কিন্তু একই list-এ **দুই গতিতে** হাঁটা যায়। দুই pointer-এর গতির অনুপাত নিজেই length মেপে দেয় — আলাদা করে আগে length গুনতে হয় না, এক পাসেই মাঝ পাওয়া যায়।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
সরল চিন্তা: আগে পুরো list একবার ঘুরে **length** `n` গুনে নাও। তারপর আবার head থেকে শুরু করে `n // 2` ঘর এগিয়ে গিয়ে সেই node return করো।
```text
pass 1: 1->2->3->4->5 গুনে n = 5
pass 2: n//2 = 2 ঘর এগোও → node 3
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
এটা ঠিক উত্তর দেয়, কিন্তু list-এর উপর **দুবার** হাঁটে (একবার গুনতে, একবার পৌঁছাতে) — মোট ~2n কাজ। slow/fast দিয়ে **একবারেই** হয়ে যায়, কারণ গতির অনুপাত নিজেই গুনে রাখে। বড় list বা streaming data-তে এক-পাস সমাধানই কাম্য।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: মাঝ খুঁজতে length জানার দরকার **নেই**। দুটো pointer-এর গতি ১:২ রাখলেই দ্রুতজন শেষে পৌঁছানোর মুহূর্তে ধীরজন আপনাআপনি মাঝে থাকে। গতির অনুপাতই length-এর কাজ করে দেয়।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
`slow` আর `fast` দুটোকেই head থেকে ছাড়ো। প্রতি step-এ `slow` ১ ঘর, `fast` ২ ঘর। `while fast and fast.next:` শর্ত রাখো — মানে fast নিরাপদে দুই ঘর লাফাতে পারবে কিনা। loop শেষ হলে `slow`-ই মাঝ। জোড় দৈর্ঘ্যে এই শর্ত স্বয়ংক্রিয়ভাবে **দ্বিতীয়** মাঝ দেয়।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "length গুনে অর্ধেকে যাব" না ভেবে ভাবো — "একজনকে দ্বিগুণ জোরে ছেড়ে দিই; ও শেষে গেলে অন্যজন এমনিতেই মাঝে।" গোনা বাদ, গতি দিয়ে কাজ — এক পাসেই শেষ।
### ছবিতে বোঝা {#7-visual-explanation}
`slow` ১ ঘর, `fast` ২ ঘর। `1->2->3->4->5` (বিজোড়):
```text
শুরু: slow=1, fast=1
step 1: slow=2, fast=3
step 2: slow=3, fast=5
fast.next = None → থামো
slow = 3 ← মাঝ ✓
1->2->3->4->5->6 (জোড়):
step 1: slow=2, fast=3
step 2: slow=3, fast=5
step 3: slow=4, fast=None (5.next.next = None)
fast = None → থামো
slow = 4 ← দ্বিতীয় মাঝ ✓
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `1 -> 2 -> 3 -> 4` (জোড়, ৪টা):
1. শুরু: `slow=1`, `fast=1`
2. `fast` ও `fast.next` আছে → `slow=2`, `fast=3`
3. `fast` আছে, `fast.next` আছে → `slow=3`, `fast=None` (3.next.next = None)
4. `fast=None` → loop শেষ
5. return `slow` = `3` → অর্থাৎ `3 -> 4` (দুই মাঝ 2,3-এর দ্বিতীয়টা)
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def middle_node(head):
slow = fast = head
while fast and fast.next: # fast দুই ঘর লাফাবে, তাই দুটোই থাকা চাই
slow = slow.next # ১ ঘর
fast = fast.next.next # ২ ঘর
return slow # fast শেষে → slow ঠিক মাঝে
# ---- helpers (test-এর জন্য) ----
def build(values):
dummy = ListNode()
tail = dummy
for v in values:
tail.next = ListNode(v)
tail = tail.next
return dummy.next
def to_list(head):
out = []
while head:
out.append(head.val)
head = head.next
return out
# ---- tests ----
assert to_list(middle_node(build([1, 2, 3, 4, 5]))) == [3, 4, 5] # বিজোড় → আসল মাঝ
assert to_list(middle_node(build([1, 2, 3, 4, 5, 6]))) == [4, 5, 6] # জোড় → দ্বিতীয় মাঝ
assert to_list(middle_node(build([1]))) == [1] # একটা node
assert to_list(middle_node(build([1, 2]))) == [2] # জোড় → দ্বিতীয়টা
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `slow = fast = head` — দুজনেই head থেকে শুরু।
- `while fast and fast.next:` — `fast` দুই ঘর লাফায়, তাই `fast` ও `fast.next` দুটোই থাকতে হবে; নাহলে শেষ ছুঁয়েছে।
- `slow = slow.next` — ধীরজন ১ ঘর।
- `fast = fast.next.next` — দ্রুতজন ২ ঘর।
- `return slow` — loop শেষে `fast` শেষপ্রান্তে, তাই `slow` মাঝে। জোড় দৈর্ঘ্যে শর্তের গঠনই দ্বিতীয় মাঝ দেয়।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`build([1,2,3,4,5])` বানায় `1->2->3->4->5`; `middle_node` ফেরায় node `3`, তাই `to_list` দেয় `[3,4,5]`। ৬-নোডের list-এ ফেরায় node `4` → `[4,5,6]`। একক node → `[1]`; দুই-নোডে দ্বিতীয়টা → `[2]`। সব 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; }
}
const arrayToList = (arr) => {
const dummy = new ListNode();
let tail = dummy;
for (const v of arr) { tail.next = new ListNode(v); tail = tail.next; }
return dummy.next;
};
const listToArray = (head) => {
const out = [];
while (head) { out.push(head.val); head = head.next; }
return out;
};
function middleNode(head) {
let slow = head, fast = head;
while (fast && fast.next) { // fast দুই ঘর লাফাবে, তাই দুটোই থাকা চাই
slow = slow.next; // ১ ঘর
fast = fast.next.next; // ২ ঘর
}
return slow; // fast শেষে -> slow ঠিক মাঝে
}
// ---- test cases ----
const eq = (a, b) => JSON.stringify(a) === JSON.stringify(b);
assert(eq(listToArray(middleNode(arrayToList([1, 2, 3, 4, 5]))), [3, 4, 5]), "বিজোড় -> আসল মাঝ");
assert(eq(listToArray(middleNode(arrayToList([1, 2, 3, 4, 5, 6]))), [4, 5, 6]), "জোড় -> দ্বিতীয় মাঝ");
assert(eq(listToArray(middleNode(arrayToList([1]))), [1]), "একটা node");
assert(eq(listToArray(middleNode(arrayToList([1, 2]))), [2]), "জোড় -> দ্বিতীয়টা");
console.log("সব JS test pass!");
```
> **JS টীকা:** `while (fast && fast.next)` শর্তটাই জোড়-দৈর্ঘ্যে **দ্বিতীয়** মাঝ দেয় — শর্ত বদলে শুধু `while (fast.next && fast.next.next)` করলে প্রথম মাঝ আসত। length আগে গুনে দুবার হাঁটার দরকার নেই; গতির অনুপাত ১:২ নিজেই length মেপে দেয়, তাই এক পাসেই মাঝ। `arrayToList`/`listToArray` helper দিয়ে snippet `node`-এ নিজে নিজে রান করে।
### TypeScript ও test cases {#26-typescript-solution-with-test-cases}
```typescript
interface ListNode { val: number; next: ListNode | null }
const arrayToList = (arr: number[]): ListNode | null => {
let head: ListNode | null = null;
for (let i = arr.length - 1; i >= 0; i--) head = { val: arr[i], next: head };
return head;
};
const listToArray = (head: ListNode | null): number[] => {
const out: number[] = [];
while (head) { out.push(head.val); head = head.next; }
return out;
};
function middleNode(head: ListNode | null): ListNode | null {
let slow: ListNode | null = head;
let fast: ListNode | null = head;
while (fast && fast.next) {
slow = slow!.next; // fast থাকলে slow-ও থাকে
fast = fast.next.next;
}
return slow;
}
function expect