Problem link ও উৎস
- **Original source:** Classic linked list exercise
- **Platform:** LeetCode —
- **Topic:** linked list
- **Difficulty:** Medium
- **Pattern:** runner / close-the-ring
- **Basic idea inherited from:** runner gap (problem 9) + modular k (math fundamentals)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা linked list আর একটা সংখ্যা `k` দেওয়া। তোমাকে list-টাকে **ডানদিকে k ঘর rotate** করতে হবে — মানে শেষের দিকের k-টা node তুলে এনে সামনে বসাতে হবে, ক্রম ঠিক রেখে। নতুন head return করো।
```text
list : 1 -> 2 -> 3 -> 4 -> 5 , k = 2
ফল : 4 -> 5 -> 1 -> 2 -> 3
```
`k` list-এর দৈর্ঘ্যের চেয়ে বড় হতে পারে — তখন wrap করতে হবে (পুরো এক পাক ঘুরলে list অপরিবর্তিত)।
### Input ও output {#8-example-input-and-output}
```text
Input : 1 -> 2 -> 3 -> 4 -> 5 , k = 2 -> Output: 4 -> 5 -> 1 -> 2 -> 3
Input : 0 -> 1 -> 2 , k = 4 -> Output: 2 -> 0 -> 1 (4 % 3 = 1)
Edge 1 (k = 0): 1 -> 2 -> 3 , k=0 -> Output: 1 -> 2 -> 3
Edge 2 (k = L-এর গুণিতক): 1 -> 2 -> 3 , k=3 -> Output: 1 -> 2 -> 3
Edge 3 (খালি list): None , k=1 -> Output: None
Edge 4 (একটা node): 7 , k=99 -> Output: 7
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
একটা গোল চাবির রিং ভাবো, তাতে কয়েকটা চাবি ক্রমে গাঁথা। rotate করা মানে রিংটা আসলে একই — তুমি শুধু ঠিক করছ "শুরু" ধরবে কোন চাবি থেকে। তাই list-এর লেজ আর মাথা জুড়ে একটা রিং বানাও, তারপর নতুন জায়গায় রিংটা কেটে দাও — নতুন শুরু পেয়ে গেলে।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
দুটো পুরোনো idea মিলেছে:
- **Runner gap** (problem 9 — nth-from-end): শেষ থেকে গুনে একটা নির্দিষ্ট জায়গায় pointer বসানোর ভাবনা। এখানেও আমরা "শেষ থেকে k ঘর আগের" node-টা খুঁজি, যেটা হবে নতুন tail।
- **Modular arithmetic** (math fundamentals): `k % length` — কারণ length-এর গুণিতক বার ঘোরালে list একই থাকে।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
দুটো লুকানো গণিত:
- **Modulo:** length `L` হলে `k` আর `k % L` একই ফল দেয় (পুরো পাক ঘোরা = কিছুই না)। তাই প্রথমেই `k %= L` করে নিই — না করলে বড় k-তে অসংখ্য বাড়তি ঘোরা।
- **নতুন break-point:** ডানে k ঘর rotate মানে নতুন head হলো শেষ থেকে k-তম node, অর্থাৎ সামনে থেকে `L - k`-তম node। তাই নতুন tail বসে index `L - k - 1`-এ।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
কোনো নতুন structure নয় — শুধু **কয়েকটা pointer** (tail, new_tail) আর length গোনার একটা counter। O(1) extra space।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
Linked list-এ শেষ node-কে head-এর সাথে জুড়ে দেওয়া (ring বানানো) মাত্র একটা arrow সেট — O(1)। rotate মানে আসলে "ring-টা একটা নতুন জায়গায় কেটে দেওয়া"। তাই আলাদা কোনো structure লাগে না; pointer দিয়ে ring বানিয়ে, ঠিক জায়গায় কেটে দিলেই rotate হয়ে যায়।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
সরল চিন্তা: rotate-right-by-1 একটা helper বানাও (শেষ node তুলে এনে সামনে বসাও), তারপর সেটা `k` বার চালাও।
```text
1->2->3->4->5 (rotate 1) -> 5->1->2->3->4
(rotate 1) -> 4->5->1->2->3 (k=2 শেষ)
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
প্রতিবার rotate-by-1-এ শেষ node খুঁজতে পুরো list হাঁটতে হয় — O(n)। সেটা k বার করলে **O(n·k)**। k বড় হলে (বা k >> n) এটা ভয়ানক ধীর। অথচ `k % n` করলে আর ring trick ব্যবহার করলে পুরোটা **এক-দুই পাসেই** শেষ।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **rotate করা মানে list-টাকে একটা ring ধরে শুধু "শুরুর বিন্দু" সরানো।** তাই বারবার ঘোরানোর দরকার নেই — একবার ring বানিয়ে, সঠিক জায়গায় (index `L-k-1`-এর পরে) কেটে দিলেই হয়।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
প্রথমে length `L` আর tail বের করো (এক পাস)। `k %= L` করো; `k == 0` হলে কিছুই বদলায় না, head ফেরাও। নাহলে `tail.next = head` দিয়ে ring বানাও, head থেকে `L - k - 1` ঘর এগিয়ে new_tail-এ থামো, `new_head = new_tail.next` নাও, আর `new_tail.next = None` দিয়ে ring কেটে দাও।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "k বার ঘোরাব" না ভেবে ভাবো — "list তো আসলে একটা বৃত্ত; আমি শুধু কোথায় কাটব সেটা ঠিক করছি।" আর k বড় হলে আগে `k %= L` করে নাও, যাতে অপ্রয়োজনীয় পাক বাদ যায়। ঘোরানো বাদ, একটাই কাটা।
### ছবিতে বোঝা {#7-visual-explanation}
`1 -> 2 -> 3 -> 4 -> 5`, `k = 2` (L = 5):
```text
ধাপ ১ — length + tail: L = 5, tail = 5
ধাপ ২ — k %= L: k = 2 % 5 = 2
ধাপ ৩ — ring বানাও: 5.next = 1 (লেজ মাথায় জোড়া)
ধাপ ৪ — new_tail index = L-k-1 = 2 → node 3
new_head = new_tail.next = 4
new_tail.next = None (রিং কাটো)
ফল: 4 -> 5 -> 1 -> 2 -> 3
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `0 -> 1 -> 2`, `k = 4`:
1. Length + tail: হাঁটতে হাঁটতে `L = 3`, `tail = 2`।
2. `k %= L` → `k = 4 % 3 = 1`।
3. `k != 0`, তাই ring: `tail.next = head` → `2.next = 0`।
4. `steps = L - k - 1 = 3 - 1 - 1 = 1`; `new_tail = 0`, এক ঘর এগিয়ে `new_tail = 1`।
5. `new_head = new_tail.next = 2`; `new_tail.next = None` → ring কাটলো।
6. ফল: `2 -> 0 -> 1`।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def rotate_right(head, k):
if not head or not head.next:
return head # খালি বা একক node — rotate-এ কিছু বদলায় না
# ১) length আর শেষ node (tail) বের করো
length = 1
tail = head
while tail.next:
tail = tail.next
length += 1
# ২) k বড় হলে wrap; পুরো পাক ঘোরা = কিছুই না
k %= length
if k == 0:
return head
# ৩) ring বানিয়ে নতুন জায়গায় কাটো
tail.next = head # লেজ মাথায় জুড়ে বৃত্ত
steps = length - k - 1 # new tail এতগুলো ঘর head থেকে
new_tail = head
for _ in range(steps):
new_tail = new_tail.next
new_head = new_tail.next
new_tail.next = None # বৃত্ত কাটো
return new_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(rotate_right(build([1, 2, 3, 4, 5]), 2)) == [4, 5, 1, 2, 3]
assert to_list(rotate_right(build([0, 1, 2]), 4)) == [2, 0, 1] # 4 % 3 = 1
assert to_list(rotate_right(build([1, 2, 3]), 3)) == [1, 2, 3] # পুরো পাক
assert to_list(rotate_right(build([1, 2, 3]), 0)) == [1, 2, 3] # k = 0
assert to_list(rotate_right(build([]), 1)) == [] # খালি
assert to_list(rotate_right(build([7]), 99)) == [7] # একটা node
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `if not head or not head.next:` — খালি বা একক-node list rotate-এ অপরিবর্তিত।
- length-loop — tail-এ পৌঁছানো পর্যন্ত হেঁটে length গোনো; শেষে `tail` শেষ node-এ।
- `k %= length` — k-কে [0, L) সীমায় আনো; `k == 0` হলে কিছুই না, head ফেরাও।
- `tail.next = head` — list-কে একটা বৃত্তে বদলাও।
- `steps = length - k - 1` — new tail সামনে থেকে এতটা দূরে; এক loop-এ সেখানে যাও।
- `new_head = new_tail.next; new_tail.next = None` — নতুন head ধরো, বৃত্ত কেটে list সোজা করো।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`build([0,1,2])`, `k=4` → length 3, tail node 2। `k = 4 % 3 = 1`। ring: `2.next=0`। `steps = 1`, new_tail = node 1, new_head = node 2। `1.next=None`। ফল `2 -> 0 -> 1` → `[2,0,1]` — assert pass। বড় k, পুরো-পাক k, k=0, খালি, একক — সব pass; শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(n)** — একবার length/tail-এর জন্য হাঁটা, আরেকবার new tail-এ পৌঁছাতে আংশিক হাঁটা; মোট রৈখিক।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(1)** — শুধু কয়েকটা pointer আর একটা counter; list-এর সাইজের সাথে extra memory বাড়ে না।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- `k %= length` না করা — বড় k-তে হয় ভুল ফল, নয়তো অপ্রয়োজনীয় অসংখ্য ঘোরা।
- `steps` ভুল গোনা — `L - k` বনাম `L - k - 1` গুলিয়ে ফেলা; new_tail-কে এক ঘর বেশি/কম নিয়ে যাওয়া।
- ring কাটতে ভুলে যাওয়া (`new_tail.next = None`) — তখন list-এ cycle থেকে যায়, `to_list` infinite loop।
- খালি list বা `head.next is None` আলাদা করে না ভাবা — length-loop বা modulo-তে সমস্যা।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: runner/gap চিন্তা ([[009-remove-nth-from-end.md](009-remove-nth-from-end.md)](009-remove-nth-from-end.md) — শেষ থেকে গুনে জায়গা ঠিক করা) আর modular arithmetic (math fundamentals)। আটকে গেলে "শেষ থেকে k-তম কোথায়" — এই প্রশ্নে ফিরে যাও।
### পরের অনুশীলন {#22-similar-harder-problems}
- Rotate Array (একই idea array-তে) —