Problem link ও উৎস
- **Original source:** Classic linked list exercise
- **Platform:** LeetCode —
- **Topic:** linked list
- **Difficulty:** Medium
- **Pattern:** runner + dummy head (fixed-gap two pointers)
- **Basic idea inherited from:** slow/fast (problem 3, 4), কিন্তু গতির অনুপাতের বদলে একটা স্থির gap
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা singly linked list দেওয়া আর একটা সংখ্যা `n`। তোমাকে **শেষ থেকে** গুনে `n` নম্বর node-টা মুছে দিতে হবে, আর সেটা মাত্র **একবার** list-এর উপর হেঁটে। নতুন head return করো।
```text
list: 1 -> 2 -> 3 -> 4 -> 5 , n = 2
শেষ থেকে 2য় = node 4 , মুছে ফেলো
ফল : 1 -> 2 -> 3 -> 5
```
### Input ও output {#8-example-input-and-output}
```text
Input : 1 -> 2 -> 3 -> 4 -> 5 , n = 2 -> Output: 1 -> 2 -> 3 -> 5
Edge 1 (head মুছে যায়): 1 -> 2 , n = 2 -> Output: 2
Edge 2 (একটা node) : 1 , n = 1 -> Output: None (খালি)
Edge 3 (শেষটা মুছে) : 1 -> 2 -> 3 , n = 1 -> Output: 1 -> 2
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো দুজন একই গতিতে হাঁটছে, কিন্তু একজন আরেকজনের চেয়ে ঠিক `n` কদম এগিয়ে। সামনেরজন যখন রাস্তার শেষ মাথায় পৌঁছায়, পিছনেরজন তখন ঠিক "শেষ থেকে `n` কদম" দূরত্বে দাঁড়িয়ে — মাপজোক ছাড়াই দূরত্বটা ধরে রাখা গেল।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এর শিকড় problem 3 আর 4-এর **দুই-pointer** খেলায়। তবে সেখানে গতি ছিল ভিন্ন (এক ঘর বনাম দুই ঘর); এখানে দুজনের গতি **একই**, কিন্তু তাদের মধ্যে একটা **স্থির ফাঁক** (gap) `n` ঘরের। এই "fixed gap" idea-টাই নতুন — runner pattern-এর আরেকটা রূপ।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো অঙ্ক সরল: যদি দুটো pointer-এর মধ্যে ঠিক `n` ঘরের দূরত্ব রাখি আর সামনেরজন list-এর **শেষে** (None) পৌঁছায়, তখন পিছনেরজন থাকবে ঠিক শেষ থেকে `n` নম্বর node-এ। মুছতে হলে আবার তার **আগের** node দরকার, তাই dummy থেকে শুরু করে gap-টা `n + 1` রাখি — তাহলে পিছনেরজন থামে মুছে-ফেলা node-এর ঠিক আগে।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
কোনো extra structure নয় — শুধু একটা **dummy head** আর **দুটো pointer** (`fast`, `slow`)। dummy থাকায় আসল head মুছে ফেললেও আলাদা special case সামলাতে হয় না।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
Linked list-এ আমরা শেষ থেকে index করতে পারি না, length-ও আগে জানা নেই। কিন্তু দুটো pointer-এর মধ্যে একটা স্থির gap রাখলে সামনেরজনই length-এর কাজ মেপে দেয় — পিছনেরজন আপনাআপনি সঠিক জায়গায় থামে। dummy head-টা O(1)-তে head-মোছা case সহজ করে দেয়।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
সরল চিন্তা: প্রথমে পুরো list একবার ঘুরে **length** `L` গোনো। তারপর আবার head থেকে শুরু করে `L - n` ঘর এগিয়ে গিয়ে সেই node-এর আগেরটায় থামো, আর তার `next` bypass করো।
```text
pass 1: 1->2->3->4->5 গুনে L = 5
pass 2: L - n = 3 ঘর এগিয়ে node 3-এ থামো, 3.next bypass
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
এটা ঠিক উত্তর দেয়, কিন্তু list-এর উপর **দুবার** হাঁটে (একবার গুনতে, একবার পৌঁছাতে)। problem নিজেই বলছে এক পাসে করতে — runner + fixed gap দিয়ে এক পাসেই হয়ে যায়, কারণ gap-টাই length-এর হিসাব রেখে দেয়।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: শেষ থেকে দূরত্ব মাপতে length গোনার দরকার **নেই**। দুটো pointer-এর মধ্যে `n` ঘরের ফাঁক রেখে দিলে, সামনেরজন শেষ ছোঁয়ার মুহূর্তে পিছনেরজন আপনাআপনি শেষ থেকে `n` নম্বরে থাকে।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
dummy থেকে দুজনকে শুরু করো। `fast` কে আগে `n + 1` ঘর এগিয়ে দাও (যাতে gap শেষে মুছে-ফেলা node-এর আগের জায়গায় বসে)। তারপর `fast` None না হওয়া পর্যন্ত দুজনে একসাথে এগোও। থামলে `slow` থাকবে target-এর ঠিক আগে — `slow.next = slow.next.next` করে bypass করে দাও।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "length গুনে L − n-এ যাব" না ভেবে ভাবো — "দুজনের মধ্যে n+1 ঘরের ফাঁক বানাই, সামনেরজনকে প্রান্তে ছেড়ে দিই; ও শেষে গেলে পিছনেরজন এমনিতেই কাটার ঠিক আগে।" গোনা বাদ, ফাঁক দিয়ে কাজ।
### ছবিতে বোঝা {#7-visual-explanation}
`fast` কে আগে `n + 1` ঘর এগোও, তারপর দুজনে একসাথে। `1->2->3->4->5`, `n = 2`:
```text
dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> None
fast কে n+1 = 3 ঘর এগোও:
slow=dummy, fast=3
একসাথে এগোও (fast শেষ না হওয়া পর্যন্ত):
slow=1, fast=4
slow=2, fast=5
slow=3, fast=None ← থামো
slow = 3 , মুছতে হবে slow.next = 4
slow.next = slow.next.next → 3 -> 5
ফল: 1 -> 2 -> 3 -> 5
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `1 -> 2 -> 3 -> 4 -> 5`, `n = 2`:
1. `dummy -> 1 -> ... -> 5`; `slow = fast = dummy`
2. `fast` কে `n + 1 = 3` ঘর এগোও → `fast = 3`, `slow = dummy`
3. একসাথে: `fast = 4`, `slow = 1`
4. একসাথে: `fast = 5`, `slow = 2`
5. একসাথে: `fast = None`, `slow = 3` → থামো
6. `slow.next` (= 4) bypass: `slow.next = slow.next.next` → `3 -> 5`
7. return `dummy.next` = `1 -> 2 -> 3 -> 5`
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def remove_nth_from_end(head, n):
dummy = ListNode(0, head) # dummy: head মুছলেও special case এড়ায়
slow = fast = dummy
for _ in range(n + 1): # fast কে n+1 ঘর এগোও (gap বানাও)
fast = fast.next
while fast: # দুজনে একসাথে; fast শেষে গেলে slow কাটার আগে
fast = fast.next
slow = slow.next
slow.next = slow.next.next # target node bypass করো
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(remove_nth_from_end(build([1, 2, 3, 4, 5]), 2)) == [1, 2, 3, 5]
assert to_list(remove_nth_from_end(build([1, 2]), 2)) == [2] # head মুছে যায়
assert to_list(remove_nth_from_end(build([1]), 1)) == [] # একমাত্র node
assert to_list(remove_nth_from_end(build([1, 2, 3]), 1)) == [1, 2] # শেষটা মুছে
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `dummy = ListNode(0, head)` — নকল head; আসল head মুছলেও যাতে আলাদা করে ভাবতে না হয়।
- `slow = fast = dummy` — দুজনেই dummy থেকে শুরু, gap শূন্য।
- `for _ in range(n + 1):` — `fast` কে `n + 1` ঘর এগোই, যাতে শেষে gap কাটার আগের জায়গায় বসে।
- `while fast:` — `fast` None না হওয়া পর্যন্ত দুজনে এক ঘর করে একসাথে এগোয়।
- `slow.next = slow.next.next` — `slow` এখন target-এর আগে; তার পরেরটা (target) bypass।
- `return dummy.next` — আসল (সম্ভবত বদলানো) head।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`build([1,2,3,4,5])` বানায় `1->2->3->4->5`; `n=2`-তে node 4 মুছে `[1,2,3,5]`। `[1,2]`, `n=2`-তে head মুছে `[2]`। `[1]`, `n=1`-তে list খালি → `[]`। `[1,2,3]`, `n=1`-তে শেষটা মুছে `[1,2]`। সব assert pass → `সব 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; }
}
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 removeNthFromEnd(head, n) {
const dummy = new ListNode(0, head); // dummy: head মুছলেও special case এড়ায়
let slow = dummy, fast = dummy;
for (let i = 0; i < n + 1; i++) fast = fast.next; // fast কে n+1 ঘর এগোও
while (fast) { fast = fast.next; slow = slow.next; } // একসাথে এগোও
slow.next = slow.next.next; // target node bypass করো
return dummy.next;
}
// ---- test cases ----
const eq = (a, b) => JSON.stringify(a) === JSON.stringify(b);
assert(eq(listToArray(removeNthFromEnd(arrayToList([1, 2, 3, 4, 5]), 2)), [1, 2, 3, 5]), "main");
assert(eq(listToArray(removeNthFromEnd(arrayToList([1, 2]), 2)), [2]), "head মুছে যায়");
assert(eq(listToArray(removeNthFromEnd(arrayToList([1]), 1)), []), "একমাত্র node");
assert(eq(listToArray(removeNthFromEnd(arrayToList([1, 2, 3]), 1)), [1, 2]), "শেষটা মুছে");
console.log("সব JS test pass!");
```
> **JS টীকা:** `new ListNode(0, head)` দিয়ে dummy বানাই যাতে আসল head মুছে গেলেও আলাদা special case না লাগে — শেষে `dummy.next` ফেরাই। মূল চাবি: `fast`-কে `n` নয়, `n + 1` ঘর এগোতে হবে, যাতে loop শেষে `slow` মুছে-ফেলা node-এর ঠিক **আগে** থামে আর `slow.next = slow.next.next` দিয়ে bypass করা যায়। এক পাসেই হয়, length গোনা লাগে না।
### 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 removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
const dummy: ListNode = node(0, head);
let slow: ListNode = dummy;
let fast: ListNode = dummy;
for (let i = 0; i < n + 1; i++) fast = fast.next!; // n+1 ঘর (ধরে নিচ্ছি n বৈধ)
while (fast) { fast = fast.next!; slow = slow.next!; }
slow.next = slow.next!.next;
return dummy.next;
}
function expect