Problem link ও উৎস
- **Original source:** Classic linked list exercise
- **Platform:** LeetCode —
- **Topic:** linked list
- **Difficulty:** Medium
- **Pattern:** segmented reversal (head-insertion)
- **Basic idea inherited from:** full reversal (problem 1) + সাবধানে boundary সেলাই
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা linked list আর দুটো position `left` ও `right` (১ থেকে গোনা) দেওয়া। শুধু `left` থেকে `right` পর্যন্ত অংশটুকু **উল্টে** দাও, বাকিটা যেমন আছে তেমন থাকবে। এক পাসে করো। নতুন head return করো।
```text
list : 1 -> 2 -> 3 -> 4 -> 5 , left = 2 , right = 4
শুধু 2..4 উল্টাও
ফল : 1 -> 4 -> 3 -> 2 -> 5
```
### Input ও output {#8-example-input-and-output}
```text
Input : 1 -> 2 -> 3 -> 4 -> 5 , left=2 , right=4 -> Output: 1 -> 4 -> 3 -> 2 -> 5
Edge 1 (পুরোটা): 1 -> 2 -> 3 -> 4 -> 5 , left=1 , right=5 -> Output: 5 -> 4 -> 3 -> 2 -> 1
Edge 2 (এক node): 1 -> 2 -> 3 , left=2 , right=2 -> Output: 1 -> 2 -> 3 (কোনো বদল নেই)
Edge 3 (head ঘিরে): 3 -> 5 , left=1 , right=2 -> Output: 5 -> 3
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
একটা বইয়ের তাকের নির্দিষ্ট কয়েকটা বই উল্টো ক্রমে সাজাতে চাও। বাঁদিকের একটা স্থির বইকে খুঁটি ধরে, তার ঠিক ডানপাশের বইটা বারবার তুলে এনে খুঁটির পরে গুঁজে দাও — অংশটুকু উল্টে যায়, আশপাশের সাজানো বই অটুট থাকে।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এর ভিত্তি problem 1 ([[001-reverse-linked-list.md](001-reverse-linked-list.md)](001-reverse-linked-list.md))-এর **full reversal**। সেখানে পুরো list উল্টানো হয়; এখানে শুধু একটা **অংশ**। নতুন চ্যালেঞ্জ: উল্টানো অংশের দুই প্রান্ত আবার সঠিকভাবে বাকি list-এর সাথে **সেলাই** (stitch) করা — না হলে list ভেঙে যায়।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো কৌশল **head-insertion**: `left`-এর ঠিক আগের node-কে (`prev`) একটা স্থির খুঁটি ধরে রাখো। তারপর অংশের ভেতরের প্রতিটা পরের node-কে এক এক করে তুলে এনে `prev`-এর ঠিক পরে বসাও। এতে ঠিক `right − left` বার এই "তুলে সামনে বসানো" করলে অংশটা উল্টে যায়, আর boundary দুটো আপনাআপনি ঠিক থাকে।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
কোনো extra structure নয় — একটা **dummy head** (যদি `left = 1` হয়ে head বদলায়) আর কয়েকটা pointer (`prev`, `cur`, `nxt`)। O(1) extra space।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
Linked list-এ একটা node-কে অন্য জায়গায় সরানো মানে শুধু কয়েকটা arrow বদল — O(1), data সরানো লাগে না। head-insertion ঠিক এই সুবিধাটাই খাটায়: `prev` খুঁটি স্থির রেখে ভেতরের node গুলো সামনে এনে বসানো। dummy head থাকায় `left = 1`-এর special case আলাদা সামলাতে হয় না।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
সরল চিন্তা: `left..right` অংশের value গুলো একটা array-তে নাও, array উল্টাও, তারপর সেই উল্টানো value গুলো আবার ওই অংশের node-এ বসিয়ে দাও।
```text
2..4 অংশ = [2,3,4] -> উল্টাও -> [4,3,2] -> node গুলোতে বসাও
ফল: 1 -> 4 -> 3 -> 2 -> 5
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
value-copy করলে O(k) extra space লাগে (k = অংশের দৈর্ঘ্য), আর অনেক ক্ষেত্রে value নয়, **node** উল্টানোই উদ্দেশ্য। head-insertion দিয়ে কোনো array ছাড়াই, এক পাসে, পুরোনো node গুলোর arrow ঘুরিয়েই O(1) space-এ হয়ে যায়।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: পুরো অংশ আলাদা করে উল্টে আবার জোড়ার দরকার নেই। `left`-এর আগের node-কে খুঁটি ধরে, ভেতরের পরের node-টা বারবার সামনে এনে বসালেই অংশটা উল্টে যায় — এবং দুই প্রান্তের সেলাই আপনাআপনি ঠিক থাকে।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
dummy বসিয়ে `prev` কে `left`-এর ঠিক আগের node-এ নাও (`left − 1` ঘর এগিয়ে)। `cur = prev.next` (অংশের প্রথম node, যেটা শেষে অংশের লেজ হবে)। তারপর `right − left` বার: `cur`-এর পরের node `nxt`-কে তুলে `prev`-এর পরে বসাও (`cur.next = nxt.next`, `nxt.next = prev.next`, `prev.next = nxt`)। শেষে `dummy.next`।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "অংশটা কেটে, উল্টে, আবার জুড়ব" না ভেবে ভাবো — "একটা খুঁটির পরে ভেতরের node গুলো এক এক করে সামনে এনে বসাই; ঠিক ততবার যতটা লম্বা অংশ।" তাহলে boundary সেলাই আর আলাদা করে ভাবতে হয় না।
### ছবিতে বোঝা {#7-visual-explanation}
`prev` খুঁটি, প্রতিবার `cur`-এর পরেরটা তুলে `prev`-এর পরে বসাও। `1->2->3->4->5`, `left=2, right=4`:
```text
dummy -> 1 -> 2 -> 3 -> 4 -> 5
prev = 1 (left-এর আগের node) , cur = 2
তুলে-সামনে-বসাও (right-left = 2 বার):
nxt=3: 2->4, 3->2, 1->3 → 1 -> 3 -> 2 -> 4 -> 5
nxt=4: 2->5, 4->3, 1->4 → 1 -> 4 -> 3 -> 2 -> 5
return dummy.next = 1 -> 4 -> 3 -> 2 -> 5
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `1 -> 2 -> 3 -> 4 -> 5`, `left = 2`, `right = 4`:
1. `dummy -> 1 -> 2 -> 3 -> 4 -> 5`; `prev = dummy`
2. `left − 1 = 1` ঘর এগোও → `prev = 1`; `cur = prev.next = 2`
3. বার ১: `nxt = 3`; `cur.next = nxt.next (=4)` → `2->4`; `nxt.next = prev.next (=2)` → `3->2`; `prev.next = nxt (=3)` → `1->3`; এখন `1 -> 3 -> 2 -> 4 -> 5`
4. বার ২: `nxt = 4`; `cur.next = nxt.next (=5)` → `2->5`; `nxt.next = prev.next (=3)` → `4->3`; `prev.next = nxt (=4)` → `1->4`; এখন `1 -> 4 -> 3 -> 2 -> 5`
5. `right − left = 2` বার শেষ; return `dummy.next` = `1 -> 4 -> 3 -> 2 -> 5`
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverse_between(head, left, right):
dummy = ListNode(0, head) # left=1 হলে head বদলায়, তাই dummy
prev = dummy
for _ in range(left - 1): # prev কে left-এর ঠিক আগের node-এ নাও
prev = prev.next
cur = prev.next # অংশের প্রথম node (শেষে অংশের লেজ হবে)
for _ in range(right - left): # head-insertion ঠিক ততবার
nxt = cur.next # তুলে আনার node
cur.next = nxt.next # cur অংশের বাকি/পরের দিকে
nxt.next = prev.next # nxt অংশের বর্তমান মাথার আগে
prev.next = nxt # prev এখন nxt-কে মাথা ধরে
return dummy.next
# ---- 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_between(build([1, 2, 3, 4, 5]), 2, 4)) == [1, 4, 3, 2, 5]
assert to_list(reverse_between(build([1, 2, 3, 4, 5]), 1, 5)) == [5, 4, 3, 2, 1] # পুরোটা
assert to_list(reverse_between(build([1, 2, 3]), 2, 2)) == [1, 2, 3] # এক node
assert to_list(reverse_between(build([3, 5]), 1, 2)) == [5, 3] # head ঘিরে
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `dummy = ListNode(0, head)` — `left = 1`-এ head বদলালেও সহজে ফেরাতে।
- `for _ in range(left - 1):` — `prev` কে `left`-এর ঠিক আগের node-এ নিয়ে যাও।
- `cur = prev.next` — উল্টানো অংশের প্রথম node; এটাই শেষে অংশের লেজ।
- `for _ in range(right - left):` — head-insertion ঠিক `right − left` বার।
- `nxt = cur.next` — যে node-টা তুলে সামনে আনব।
- `cur.next = nxt.next` — `cur` কে `nxt`-এর পরেরটার সাথে জোড়ো (লেজ হারায় না)।
- `nxt.next = prev.next` — `nxt` কে অংশের বর্তমান মাথার আগে বসাও।
- `prev.next = nxt` — `prev` এখন নতুন মাথা `nxt`-কে ধরে।
- `return dummy.next` — আসল (সম্ভবত বদলানো) head।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`build([1,2,3,4,5])`-এ `left=2,right=4` দিলে দুই বার head-insertion-এ `[1,4,3,2,5]`। `left=1,right=5` হলে পুরোটা উল্টে `[5,4,3,2,1]`। `left=right=2`-তে শূন্য বার, কোনো বদল নেই। head ঘিরে `[3,5]`,`1,2` → `[5,3]`। সব assert pass → `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(n)** — `prev`-এ পৌঁছাতে রৈখিক, তারপর `right − left` বার head-insertion; মোট list-এর উপর এক পাস।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(1)** — শুধু dummy + কয়েকটা pointer; পুরোনো node reuse, extra memory বাড়ে না।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- তিনটা arrow ভুল ক্রমে সেট করা — `cur.next = nxt.next` আগে না করলে অংশের পরের node হারায়।
- `prev` কে `left − 1`-এর বদলে `left` ঘর এগিয়ে নেওয়া — তখন উল্টানো এক ঘর সরে যায়।
- `left = 1` (head বদলায়) case-এর জন্য dummy না নেওয়া।
- loop চালানো `right − left + 1` বার (এক বার বেশি) — boundary ভেঙে যায়; ঠিক `right − left` বার।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: problem 1 ([[001-reverse-linked-list.md](001-reverse-linked-list.md)](001-reverse-linked-list.md))-এর full reversal; তার উপর head-insertion + boundary সেলাই যোগ করে অংশ-উল্টানো। dummy head কৌশল problem 2 ([[002-merge-two-sorted-lists.md](002-merge-two-sorted-lists.md)](002-merge-two-sorted-lists.md)) থেকে।
### পরের অনুশীলন {#22-similar-harder-problems}
- Reverse Linked List (পুরোটা) —