Problem link ও উৎস
- **Original source:** Classic capstone interview problem (presented two ways in one sitting)
- **Platform:** LeetCode —
- **Topic:** linked lists + recursion
- **Difficulty:** Easy
- **Pattern:** Pointer surgery — iterative three-pointer AND recursive rewiring
- **Basic idea inherited from:** এটা একটা cross-topic capstone — এখানে মেশে **03 linked lists** (node-এর `next` arrow ঘোরানো, pointer surgery) আর **06 recursion** (একই কাজকে call stack দিয়ে করা: লেজ আগে উল্টাও, তারপর নিজের link ঠিক করো)। mock-এ এর শর্ত: **এক বসায় দুই রূপই** লেখা।
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা singly linked list দেওয়া — কতগুলো node, প্রতিটা পরেরটার দিকে `next` arrow দিয়ে তাকিয়ে। সব arrow **উল্টে** দাও, যাতে শেষ node প্রথম হয়, প্রথমটা শেষ। নতুন head return করো। এই capstone-এ তোমাকে **দুইভাবে** করতে হবে — একবার iterative (লুপ), একবার recursive (call stack)।
```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}
একটা ট্রেনের বগি ভাবো, প্রতিটা সামনের বগির সাথে যুক্ত, তুমি পুরো ট্রেন উল্টো দিকে চালাতে চাও।
- Iterative = তুমি সামনে থেকে এক এক করে সংযোগ খুলে উল্টো দিকে জুড়ছ, খোলার আগে পরের বগি মনে রাখছ (`nxt`)।
- Recursive = তুমি ভেতরে হেঁটে গিয়ে আগে শেষ বগিতে পৌঁছাও, তারপর ফেরার পথে প্রতিটা সংযোগ পেছনে জুড়তে জুড়তে আসো — call stack-ই তোমাকে ফেরার পথ মনে রাখায়।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এই problem দুটো আগের chapter-এর tool জোড়া দেয়:
- **03 linked lists** থেকে: এক জোড়া node-এর arrow ঘোরানো (`a -> b` কে `a <- b`), তিন pointer দিয়ে নিরাপদে link rewiring।
- **06 recursion** থেকে: একই কাজকে "আগে বাকি লেজটা উল্টাও (recursive call), তারপর শুধু এই node-এর link ঠিক করো" — base case + এক ধাপ + বিশ্বাস যে ছোট অংশ ঠিক হয়ে এসেছে।
iterative রূপ পুরোটা 04; recursive রূপ 04-এর arrow surgery-কে 06-এর call stack-এ বসায়। দুটো লেখাই এই combo চেনার drill।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic একটা **invariant** (iterative-এ) আর একটা **induction** (recursive-এ):
- Iterative: `prev` সবসময় এ পর্যন্ত উল্টানো অংশের head, `cur` না-ছোঁয়া অংশের head। প্রতি step এই invariant ধরে রাখে।
- Recursive: ধরে নাও `reverse(head.next)` লেজটা ঠিকঠাক উল্টে দিয়েছে; তখন শুধু `head.next.next = head` (পরের node-কে নিজের দিকে ফেরাও) আর `head.next = None` করলেই পুরো জিনিস উল্টে যায়। এটাই mathematical induction-এর "ছোট ক্ষেত্র ঠিক ⇒ বড় ক্ষেত্র ঠিক"।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
কোনো extra data structure লাগে না।
- Iterative: **তিনটা pointer** (`prev`, `cur`, `nxt`) — O(1) extra space।
- Recursive: কোনো explicit structure নেই, কিন্তু **call stack** O(n) গভীর হয় (06 recursion-এর দাম)।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
Linked list-এ node গুলো memory-তে ছড়ানো, শুধু `next` arrow দিয়ে বাঁধা — তাই index না করে আমরা **arrow নিজে বদলাই**। iterative-এ তিন pointer দিয়ে link এক এক করে নিরাপদে ঘোরে, কোনো node না হারিয়ে। recursive-এ call stack নিজেই "পরের node কোথায়" মনে রেখে দেয়, তাই আলাদা `nxt` লাগে না — 06 recursion-এর সাথে এই কারণে খাপ খায়।
## ধাপে ধাপে সমাধান {#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 উল্টানো (iterative-এ O(1) space)। তাছাড়া নতুন node বানানো অপচয় — পুরনো node-এর arrow ঘোরালেই হয় (04 pointer surgery)।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **পুরো list একসাথে উল্টানোর দরকার নেই — প্রতিটা node-এর `next` কে তার আগের node-এর দিকে ঘুরিয়ে দিলেই হয়।** শুধু arrow ঘোরানোর আগে পরের node হারিয়ে না ফেলা (iterative-এ `nxt`, recursive-এ call stack এটা সামলায়)।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
- Iterative: তিন pointer নিয়ে একবার হাঁটো — পরেরটা মনে রাখো, এখনকার arrow পিছনে ঘোরাও, দুজনে এক ঘর এগোও।
- Recursive: base case (খালি বা একক node) ফেরত দাও যেমন আছে; নাহলে আগে `reverse(head.next)` দিয়ে লেজ উল্টাও, তারপর `head.next.next = head` করে নিজের পরের node-কে নিজের দিকে ফেরাও, আর `head.next = None` দিয়ে পুরনো arrow কাটো।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "list উল্টাব" ভাবার বদলে ভাবো "প্রতিটা arrow আলাদা করে পিছনে ঘোরাব।" iterative-এ পরেরটা আগে ধরে রাখি; recursive-এ লেজটা আগে উল্টিয়ে নিই, তারপর শুধু একটা link ঠিক করি — call stack বাকি মনে রাখে।
### ছবিতে বোঝা {#7-visual-explanation}
দুই রূপ পাশাপাশি, `1 -> 2 -> 3` দিয়ে:
```text
ITERATIVE (prev, cur, nxt):
শুরু: prev=None cur=1 -> 2 -> 3
step1: nxt=2; 1.next=None; prev=1, cur=2 => None<-1 2->3
step2: nxt=3; 2.next=1; prev=2, cur=3 => None<-1<-2 3
step3: nxt=None; 3.next=2; prev=3, cur=None=> None<-1<-2<-3
head = prev = 3
RECURSIVE (ভেতরে যাও, ফেরার পথে জোড়ো):
reverse(1) -> reverse(2) -> reverse(3) -> reverse(None) base
ফেরা: 3 head ধরে রাখলাম
2.next.next = 2 (3->2); 2.next=None
1.next.next = 1 (2->1); 1.next=None
head = 3
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `1 -> 2 -> 3` (iterative):
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` → থামো; 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_iterative(head):
prev = None
cur = head
while cur:
nxt = cur.next # পরেরটা আগে ধরে রাখো
cur.next = prev # arrow পিছনে ঘোরাও
prev = cur # prev এক ঘর এগোলো
cur = nxt # cur এক ঘর এগোলো
return prev # নতুন head
def reverse_recursive(head):
if head is None or head.next is None:
return head # base: খালি বা একক node নিজেই উল্টানো
new_head = reverse_recursive(head.next) # আগে লেজ উল্টাও
head.next.next = head # পরের node-কে নিজের দিকে ফেরাও
head.next = None # পুরনো arrow কাটো
return new_head # নতুন head (সবচেয়ে শেষ node) উপরে পাঠাও
# ---- 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 (দুই রূপই একই উত্তর দিতে হবে) ----
for reverse in (reverse_iterative, reverse_recursive):
assert to_list(reverse(build([1, 2, 3, 4, 5]))) == [5, 4, 3, 2, 1]
assert to_list(reverse(build([]))) == [] # খালি list
assert to_list(reverse(build([7]))) == [7] # একটা node
assert to_list(reverse(build([1, 2]))) == [2, 1] # দুই node
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
Iterative:
- `prev=None`, `cur=head` — উল্টানো অংশ খালি; না-ছোঁয়া অংশ head থেকে শুরু।
- `nxt = cur.next` — arrow ঘোরানোর **আগে** পরের node বাঁচাও।
- `cur.next = prev` — এই node-এর arrow পিছনে ঘোরাও।
- `prev=cur` / `cur=nxt` — দুজনে এক ঘর এগোয়; শেষে `return prev`।
Recursive:
- `if head is None or head.next is None: return head` — base case: খালি বা শেষ node নিজেই নতুন head।
- `new_head = reverse_recursive(head.next)` — বিশ্বাস করো লেজটা উল্টে এসেছে; `new_head` পুরো উল্টানো list-এর head।
- `head.next.next = head` — এখন `head.next` হলো লেজের শেষ node; তার `next`-কে `head`-এর দিকে ফেরাও।
- `head.next = None` — `head`-এর পুরনো forward arrow কেটে দাও (নাহলে cycle হবে)।
- `return new_head` — অপরিবর্তিত head সব level-এ উপরে পাঠাও।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`build([1,2,3,4,5])` দেয় `1->...->5`। দুই রূপই `5->4->3->2->1` বানায়, `to_list` দেয় `[5,4,3,2,1]` — assert pass। `for reverse in (...)` লুপ দুই function-এই খালি/একক/জোড়া case চালায়, সবই pass। শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(n)** দুই রূপেই — প্রতিটা node ঠিক একবার করে visit হয় ও arrow ঘোরে।
### অতিরিক্ত জায়গা {#19-space-complexity}
- Iterative: **O(1)** — শুধু তিন pointer।
- Recursive: **O(n)** — call stack list-এর গভীরতার সমান (06 recursion-এর hidden cost; খুব লম্বা list-এ stack overflow-র ঝুঁকি, তাই iterative-টা production-safe)।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- Iterative-এ `nxt` রাখার **আগেই** `cur.next = prev` করা — বাকি list হারায়।
- Recursive-এ `head.next = None` ভুলে যাওয়া — পুরনো arrow থেকে যায়, ফলে শেষে cycle তৈরি হয়।
- Recursive base case-এ শুধু `head is None` দেখা (`head.next is None` বাদ) — একক node-এ `head.next.next` crash করবে।
- শেষে `prev`-এর বদলে `cur` return করা (iterative-এ `cur` তখন None)।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: linked list traversal + এক জোড়া node-এর arrow ঘোরানো (03-এর [../../03-linked-list/](../../03-linked-list/README.md)), আর "ছোট অংশ আগে সমাধান করে, ফেরার পথে নিজের কাজ" recursion (06-এর [../../06-recursion-and-backtracking/](../../06-recursion-and-backtracking/README.md))। topic-03-এর `001-reverse-linked-list.md`-ও দেখো — এটা তার দুই-রূপ সম্প্রসারণ।
### পরের অনুশীলন {#22-similar-harder-problems}
- Reverse Linked List II (শুধু একটা অংশ উল্টানো) —