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