Problem link ও উৎস
- **Original source:** Classic linked list exercise
- **Platform:** LeetCode —
- **Topic:** linked list
- **Difficulty:** Easy
- **Pattern:** in-place reversal (pointer rewiring)
- **Basic idea inherited from:** insert-at-head বারবার করা; node-to-node pointer ঘোরানো
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা singly linked list দেওয়া আছে — মানে কতগুলো node, প্রতিটা পরেরটার দিকে একটা arrow (`next`) দিয়ে তাকিয়ে আছে। তোমার কাজ: সব arrow **উল্টে** দাও, যাতে শেষ node টা প্রথম হয়ে যায় আর প্রথমটা শেষ। নতুন head return করো।
```text
আগে : 1 -> 2 -> 3 -> 4 -> 5 -> None
পরে : 5 -> 4 -> 3 -> 2 -> 1 -> None
```
### Input ও output {#8-example-input-and-output}
```text
Input : 1 -> 2 -> 3 -> 4 -> 5
Output: 5 -> 4 -> 3 -> 2 -> 1
Edge case 1 (খালি list): Input: None -> Output: None
Edge case 2 (একটা node): Input: 7 -> Output: 7
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
একটা ট্রেনের বগি ভাবো, প্রতিটা সামনের বগির সাথে যুক্ত। তুমি চাও পুরো ট্রেন উল্টো দিকে চলুক। তুমি এক এক করে প্রতিটা সংযোগ খুলে উল্টো দিকে জুড়ছ — কিন্তু খোলার **আগে** পরের বগিটা কোথায় তা মনে রাখতে হবে, নাহলে বাকি ট্রেন হারিয়ে যাবে। সেই "মনে রাখা" = `nxt` pointer।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
মূল ভিত হলো **এক জোড়া node-এর মধ্যেকার arrow ঘোরানো**। তুমি যদি জানো কীভাবে `a -> b` কে `a <- b` বানাতে হয়, তাহলে পুরো list টা just সেই কাজটা বারবার করা। সাথে "insert-at-head" চিন্তা — প্রতিটা node কে নতুন list-এর সামনে এনে বসানো।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic একটা **invariant**: যেকোনো মুহূর্তে `prev` হলো এ পর্যন্ত উল্টে ফেলা অংশের head, আর `cur` হলো এখনো-না-ছোঁয়া অংশের head। প্রতি step-এ আমরা একটা node কে উল্টানো অংশে যোগ করি, এই invariant ধরে রেখে। Loop শেষ হলে `prev`-ই পুরো উল্টানো list-এর head।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
কোনো extra data structure লাগে না — শুধু **তিনটা pointer** (`prev`, `cur`, `nxt`)। এটাই এর সৌন্দর্য: O(1) extra space।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
Linked list-এ node গুলো memory-তে ছড়িয়ে থাকে, শুধু `next` arrow দিয়ে বাঁধা। তাই array-র মতো index করা যায় না, কিন্তু **arrow নিজে বদলানো** যায় সহজে। তিনটা pointer দিয়ে আমরা link গুলো এক এক করে নিরাপদে ঘুরিয়ে দিতে পারি — কোনো node না হারিয়ে।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: list ঘুরে সব value একটা array-তে রাখি, তারপর array উল্টে আবার নতুন list বানাই।
```text
1) list -> [1,2,3,4,5]
2) উল্টাও -> [5,4,3,2,1]
3) নতুন list বানাও
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
এটা কাজ করে, কিন্তু **O(n) extra space** নেয় (array + নতুন node গুলো)। Interview-তে আসল চ্যালেঞ্জ হলো জায়গা নষ্ট না করে, **in-place** (O(1) space) উল্টানো। তাছাড়া নতুন node বানানো অপচয় — পুরোনো node গুলোর arrow ঘোরালেই তো হয়।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **পুরো list একসাথে উল্টানোর দরকার নেই** — শুধু প্রতিটা node-এর `next` কে তার আগের node-এর দিকে ঘুরিয়ে দিলেই হয়। শুধু খেয়াল রাখতে হবে, arrow ঘোরানোর আগে পরের node-টা হারিয়ে না ফেলি।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
তিনটা pointer নিয়ে list-এর উপর একবার হাঁটো। প্রতি ধাপে: পরের node মনে রাখো (`nxt`), এখনকার node-এর arrow পিছনে ঘোরাও (`cur.next = prev`), তারপর `prev` আর `cur` কে এক ঘর এগিয়ে দাও। একবার পাস শেষ — list উল্টে গেছে।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "list উল্টাব" ভাবার বদলে ভাবো "প্রতিটা arrow আলাদা করে পিছনে ঘোরাব, আর হারানো ঠেকাতে পরেরটা আগে ধরে রাখব।" বড় কাজটা একটা ছোট, repeatable step-এ ভেঙে যায়।
### ছবিতে বোঝা {#7-visual-explanation}
`prev`, `cur`, `nxt` তিনজনের নাচ। `1 -> 2 -> 3` দিয়ে দেখি:
```text
শুরু: prev=None cur=1 -> 2 -> 3 -> None
step 1: nxt = 2 (মনে রাখলাম)
1.next = None (arrow উল্টালো)
prev=1, cur=2
অবস্থা: None <- 1 2 -> 3 -> None
step 2: nxt = 3
2.next = 1
prev=2, cur=3
অবস্থা: None <- 1 <- 2 3 -> None
step 3: nxt = None
3.next = 2
prev=3, cur=None
অবস্থা: None <- 1 <- 2 <- 3
cur = None → থামো। নতুন head = prev = 3
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `1 -> 2 -> 3`:
1. শুরু: `prev=None`, `cur=1`
2. `nxt=2`; `1.next=None`; `prev=1`, `cur=2` → উল্টানো অংশ: `1`
3. `nxt=3`; `2.next=1`; `prev=2`, `cur=3` → উল্টানো অংশ: `2 -> 1`
4. `nxt=None`; `3.next=2`; `prev=3`, `cur=None` → উল্টানো অংশ: `3 -> 2 -> 1`
5. `cur=None` → loop শেষ। return `prev` = `3`
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverse_list(head):
prev = None
cur = head
while cur:
nxt = cur.next # পরেরটা আগে ধরে রাখো (নাহলে হারাবে)
cur.next = prev # arrow পিছনে ঘোরাও
prev = cur # prev এক ঘর এগোলো
cur = nxt # cur এক ঘর এগোলো
return prev # নতুন head
# ---- 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(reverse_list(build([1, 2, 3, 4, 5]))) == [5, 4, 3, 2, 1]
assert to_list(reverse_list(build([]))) == [] # খালি list
assert to_list(reverse_list(build([7]))) == [7] # একটা node
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `prev = None` — শুরুতে উল্টানো অংশ খালি, তাই এর head None।
- `cur = head` — না-ছোঁয়া অংশ শুরু হয় আসল head থেকে।
- `while cur:` — যতক্ষণ ছোঁয়ার মতো node আছে।
- `nxt = cur.next` — arrow ঘোরানোর **আগে** পরের node বাঁচিয়ে রাখো।
- `cur.next = prev` — এই node-এর arrow পিছনে (উল্টানো অংশের দিকে) ঘোরাও।
- `prev = cur` / `cur = nxt` — দুজনেই এক ঘর সামনে।
- `return prev` — loop শেষে `prev` পুরো উল্টানো list-এর head।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`build([1,2,3,4,5])` বানায় `1->2->3->4->5`। `reverse_list` সেটাকে `5->4->3->2->1` করে, `to_list` সেটাকে `[5,4,3,2,1]` বানায় — assert pass। খালি ও একক-node case-ও pass। শেষে print: `সব 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; }
}
// ---- array <-> list helper (test চালাতে) ----
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 reverseList(head) {
let prev = null, cur = head;
while (cur) {
const nxt = cur.next; // পরেরটা আগে ধরে রাখো (নাহলে হারাবে)
cur.next = prev; // arrow পিছনে ঘোরাও
prev = cur; // prev এক ঘর এগোলো
cur = nxt; // cur এক ঘর এগোলো
}
return prev; // নতুন head
}
// ---- test cases ----
const eq = (a, b) => JSON.stringify(a) === JSON.stringify(b);
assert(eq(listToArray(reverseList(arrayToList([1, 2, 3, 4, 5]))), [5, 4, 3, 2, 1]), "main");
assert(eq(listToArray(reverseList(arrayToList([]))), []), "খালি list");
assert(eq(listToArray(reverseList(arrayToList([7]))), [7]), "একটা node");
console.log("সব JS test pass!");
```
> **JS টীকা:** linked list-এর কোনো built-in নেই, তাই ছোট একটা `ListNode` class আর `arrayToList`/`listToArray` converter দিয়ে test চালাই। মূল trick একই — তিনটা pointer (`prev`, `cur`, `nxt`), আর `const nxt = cur.next` রাখতেই হবে `cur.next = prev` করার **আগে**, নাহলে বাকি list হারিয়ে যায়। `let` দিয়ে reassignable pointer, `const nxt` দিয়ে প্রতি iteration-এর temporary।
### TypeScript ও test cases {#26-typescript-solution-with-test-cases}
```typescript
interface ListNode { val: number; next: ListNode | null }
const node = (val: number, next: ListNode | null = null): ListNode => ({ val, next });
const arrayToList = (arr: number[]): ListNode | null => {
let head: ListNode | null = null;
for (let i = arr.length - 1; i >= 0; i--) head = node(arr[i], head);
return head;
};
const listToArray = (head: ListNode | null): number[] => {
const out: number[] = [];
while (head) { out.push(head.val); head = head.next; }
return out;
};
function reverseList(head: ListNode | null): ListNode | null {
let prev: ListNode | null = null;
let cur: ListNode | null = head;
while (cur) {
const nxt: ListNode | null = cur.next;
cur.next = prev;
prev = cur;
cur = nxt;
}
return prev;
}
function expect