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