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