Problem link ও উৎস
- **Original source:** Classic linked list exercise
- **Platform:** LeetCode —
- **Topic:** linked list
- **Difficulty:** Medium
- **Pattern:** middle + reverse-half combo
- **Basic idea inherited from:** problem 1 (reversal) আর problem 4 (middle) জোড়া লাগিয়ে
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা linked list দেওয়া। এর value গুলো **সামনে থেকে আর পিছন থেকে** একই কি না বলো (palindrome) — যেমন `1 2 2 1` বা `1 2 3 2 1`। আর শর্ত: **O(1) extra space**-এ করো। `True`/`False` return করো।
```text
1 -> 2 -> 2 -> 1 palindrome → True
1 -> 2 -> 3 -> 2 -> 1 palindrome → True
1 -> 2 নয় → False
```
### Input ও output {#8-example-input-and-output}
```text
Input : 1 -> 2 -> 2 -> 1 -> Output: True (জোড় দৈর্ঘ্য)
Input : 1 -> 2 -> 3 -> 2 -> 1 -> Output: True (বিজোড়, মাঝ 3 উপেক্ষিত)
Input : 1 -> 2 -> Output: False
Edge 1 (একটা node): 1 -> Output: True
Edge 2 (খালি list) : None -> Output: True
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
একটা লম্বা ফিতের দুই মাথা মেলাতে চাও কিনা দেখতে — ফিতেটা ঠিক মাঝখানে ভাঁজ করে দুই অর্ধেক মুখোমুখি ধরো, তারপর শুরু থেকে এক এক করে মেলাও। ভাঁজ করা = মাঝ বের করে দ্বিতীয় অর্ধেক উল্টে নেওয়া; মেলানো = পাশাপাশি তুলনা।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এটা দুটো আগের problem-এর **combo**। problem 4 ([[004-middle-of-list.md](004-middle-of-list.md)](004-middle-of-list.md))-এর slow/fast দিয়ে মাঝ খোঁজা, আর problem 1 ([[001-reverse-linked-list.md](001-reverse-linked-list.md)](001-reverse-linked-list.md))-এর in-place reversal দিয়ে দ্বিতীয় অর্ধেক উল্টানো। দুটো চেনা যন্ত্র জুড়ে দিলে নতুন problem-টা সহজ হয়ে যায়।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic: list palindrome হবে **যদি এবং কেবল যদি** তার প্রথম অর্ধেক, দ্বিতীয় অর্ধেকের **উল্টোটার** সমান হয়। তাই দ্বিতীয় অর্ধেক উল্টে নিয়ে দুই অর্ধেক পাশাপাশি মিলিয়ে দেখলেই হয়। বিজোড় দৈর্ঘ্যে মাঝের একক node-টা তুলনায় কোনো প্রভাব ফেলে না, তাই সেটা নিয়ে আলাদা ভাবতে হয় না।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
কোনো নতুন structure নয় — শুধু **pointer**। slow/fast দিয়ে মাঝ, তারপর তিন-pointer reversal দিয়ে দ্বিতীয় অর্ধেক উল্টানো, শেষে দুই pointer দিয়ে তুলনা। সব O(1) space।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
সহজ পথ হলো সব value একটা list/array-তে নিয়ে দুই দিক থেকে মেলানো — কিন্তু সেটা O(n) space। linked list-এ আমরা একই node-এ দুই গতিতে হেঁটে মাঝ পাই, আর arrow ঘুরিয়ে in-place উল্টাই — তাই কোনো array ছাড়াই, শুধু pointer দিয়ে O(1) space-এ পুরো কাজ হয়।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
সরল চিন্তা: list ঘুরে সব value একটা array-তে নাও, তারপর array-টা তার উল্টোটার সমান কি না দেখো (দুই দিক থেকে দুই pointer মেলাও)।
```text
1->2->2->1 => [1,2,2,1]
[1,2,2,1] == [1,2,2,1][::-1] ? → True
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
সময় O(n) ঠিকই, কিন্তু **space O(n)** — সব value array-তে রাখতে হয়। problem-এর আসল চ্যালেঞ্জ O(1) space। মাঝ + অর্ধেক-উল্টানো পদ্ধতি কোনো array ছাড়াই, শুধু pointer দিয়ে একই উত্তর দেয়।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: পুরো list মনে রাখার দরকার নেই। দ্বিতীয় অর্ধেক **জায়গাতেই** উল্টে নিলে, প্রথম অর্ধেকের সাথে পাশাপাশি মেলানো যায় — extra memory ছাড়াই।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
খালি বা একক node হলে সরাসরি `True`। নাহলে slow/fast দিয়ে মাঝ বের করো (`slow` দ্বিতীয় অর্ধেকের শুরুতে থামে)। `slow` থেকে শুরু করে তিন-pointer reversal-এ দ্বিতীয় অর্ধেক উল্টাও। তারপর `left = head`, `right = উল্টানো মাথা` — `right` শেষ না হওয়া পর্যন্ত value মেলাও; কোথাও না মিললে `False`, নাহলে `True`।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "দুই দিক থেকে মেলাব কিন্তু পিছনে তো হাঁটা যায় না" — এই দেয়াল ভাঙো দ্বিতীয় অর্ধেক উল্টে দিয়ে। তখন "পিছন থেকে" হাঁটাটাই "সামনে থেকে" হয়ে যায়, আর দুই চেনা যন্ত্র (মাঝ + reversal) জুড়ে কাজ শেষ।
### ছবিতে বোঝা {#7-visual-explanation}
মাঝ বের করো → দ্বিতীয় অর্ধেক উল্টাও → দুই অর্ধেক মেলাও। `1->2->2->1`:
```text
মাঝ (slow/fast): slow থামে দ্বিতীয় অর্ধেকের শুরুতে (2য় 2)
1 -> 2 -> [2 -> 1]
দ্বিতীয় অর্ধেক উল্টাও:
প্রথম অর্ধেক: 1 -> 2
উল্টানো দ্বিতীয়: 1 -> 2
মেলাও (left=head, right=উল্টানো মাথা):
1 == 1 ✓
2 == 2 ✓ → True
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `1 -> 2 -> 2 -> 1`:
1. খালি/একক নয় → এগোও
2. মাঝ: `slow=1,fast=1` → `slow=2(২য়),fast=2(৩য়)` → `fast.next.next = None` থামো; `slow` = ৩য় node (মান 2)
3. দ্বিতীয় অর্ধেক (`slow` থেকে `2 -> 1`) উল্টাও → `1 -> 2`; মাথা `prev` = শেষ node (মান 1)
4. মেলাও: `left = head (1)`, `right = prev (1)` → `1 == 1` ✓; `left = 2`, `right = 2`
5. `2 == 2` ✓; `right` এর পরেরটা শেষ → loop শেষ
6. কোথাও mismatch হয়নি → return `True`
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def is_palindrome(head):
if not head or not head.next:
return True # খালি বা একক node — সবসময় palindrome
slow = fast = head # মাঝ খোঁজা (problem 4)
while fast and fast.next:
slow = slow.next
fast = fast.next.next
prev = None # দ্বিতীয় অর্ধেক উল্টানো (problem 1)
cur = slow
while cur:
nxt = cur.next
cur.next = prev
prev = cur
cur = nxt
left, right = head, prev # দুই অর্ধেক মেলানো
while right: # উল্টানো অর্ধেকটাই ছোট/সমান, তাই এটাই শর্ত
if left.val != right.val:
return False
left = left.next
right = right.next
return True
# ---- helpers (test-এর জন্য) ----
def build(values):
dummy = ListNode()
tail = dummy
for v in values:
tail.next = ListNode(v)
tail = tail.next
return dummy.next
# ---- tests ----
assert is_palindrome(build([1, 2, 2, 1])) is True # জোড় palindrome
assert is_palindrome(build([1, 2, 3, 2, 1])) is True # বিজোড় palindrome
assert is_palindrome(build([1, 2])) is False # palindrome নয়
assert is_palindrome(build([1])) is True # একক node
assert is_palindrome(build([])) is True # খালি
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `if not head or not head.next:` — খালি বা একক node সবসময় palindrome → সরাসরি `True`।
- `slow = fast = head` ... `while fast and fast.next:` — slow/fast দিয়ে মাঝ; loop শেষে `slow` দ্বিতীয় অর্ধেকের শুরুতে।
- `prev = None; cur = slow; while cur:` — তিন-pointer reversal-এ দ্বিতীয় অর্ধেক জায়গাতেই উল্টায়; `prev` উল্টানো অর্ধেকের মাথা।
- `left, right = head, prev` — `left` সামনের অর্ধেক, `right` উল্টানো পিছনের অর্ধেক।
- `while right:` — উল্টানো অর্ধেকটা প্রথম অর্ধেকের সমান/ছোট, তাই এটা শেষ হলেই থামা নিরাপদ।
- `if left.val != right.val: return False` — কোথাও না মিললে palindrome নয়।
- `return True` — পুরো মিলেছে।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`build([1,2,2,1])`: মাঝ পেয়ে দ্বিতীয় অর্ধেক `1->2` করে দুই অর্ধেক মেলে → `True`। `[1,2,3,2,1]`-এ মাঝের 3 উপেক্ষিত, বাকি মেলে → `True`। `[1,2]` মেলে না → `False`। একক ও খালি → `True`। সব 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;
};
function isPalindrome(head) {
if (!head || !head.next) return true; // খালি বা একক node — সবসময় palindrome
let slow = head, fast = head; // মাঝ খোঁজা (slow/fast)
while (fast && fast.next) { slow = slow.next; fast = fast.next.next; }
let prev = null, cur = slow; // দ্বিতীয় অর্ধেক উল্টানো
while (cur) { const nxt = cur.next; cur.next = prev; prev = cur; cur = nxt; }
let left = head, right = prev; // দুই অর্ধেক মেলানো
while (right) { // উল্টানো অর্ধেকই ছোট/সমান
if (left.val !== right.val) return false;
left = left.next; right = right.next;
}
return true;
}
// ---- test cases ----
assert(isPalindrome(arrayToList([1, 2, 2, 1])) === true, "জোড় palindrome");
assert(isPalindrome(arrayToList([1, 2, 3, 2, 1])) === true, "বিজোড় palindrome");
assert(isPalindrome(arrayToList([1, 2])) === false, "palindrome নয়");
assert(isPalindrome(arrayToList([1])) === true, "একক node");
assert(isPalindrome(arrayToList([])) === true, "খালি");
console.log("সব JS test pass!");
```
> **JS টীকা:** তিনটা চেনা step একসাথে — slow/fast দিয়ে মাঝ, তিন-pointer reversal দিয়ে দ্বিতীয় অর্ধেক উল্টানো, তারপর তুলনা — সব O(1) extra space-এ (array নেওয়া হয় না)। value তুলনায় `!==` ব্যবহার করো (`!==`/`===`), `Object.is` বা reference নয়। loop-শর্ত `while (right)` রাখাই নিরাপদ কারণ উল্টানো দ্বিতীয় অর্ধেক প্রথম অর্ধেকের সমান বা ছোট, তাই সেটা শেষ হলেই থামা ঠিক।
### 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;
};
function isPalindrome(head: ListNode | null): boolean {
if (!head || !head.next) return true;
let slow: ListNode = head;
let fast: ListNode | null = head;
while (fast && fast.next) { slow = slow.next!; fast = fast.next.next; }
let prev: ListNode | null = null;
let cur: ListNode | null = slow;
while (cur) { const nxt: ListNode | null = cur.next; cur.next = prev; prev = cur; cur = nxt; }
let left: ListNode | null = head;
let right: ListNode | null = prev;
while (right) {
if (left!.val !== right.val) return false;
left = left!.next; right = right.next;
}
return true;
}
function expect