005 — Remove Duplicates from Sorted List¶

Source¶

Original source: Classic linked list exercise
Platform: LeetCode — https://leetcode.com/problems/remove-duplicates-from-sorted-list/
Topic: linked list
Difficulty: Easy
Pattern: pointer rewiring
Basic idea inherited from: delete-after-node operation + traversal

1. Problem in simple words¶

একটা sorted (ছোট-থেকে-বড় সাজানো) linked list দেওয়া। এতে পরপর একই value কয়েকবার আসতে পারে। তোমার কাজ: প্রতিটা value যেন ঠিক একবার থাকে — বাড়তি ডুপ্লিকেট গুলো সরিয়ে দাও। আসল head return করো।

আগে : 1 -> 1 -> 2 -> 3 -> 3
পরে : 1 -> 2 -> 3

2. Which basic idea does this inherit from?¶

ভিত্তি দুটো: সাধারণ traversal (list ধরে হাঁটা) আর delete-after-node operation — মানে "একটা node-এর পরেরটা বাইপাস করে দাও।" topic-এর ../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 নেই।

6. Real-life analogy¶

একটা গেস্ট-লিস্ট ভাবো যেটা নামের বর্ণক্রমে সাজানো, আর কেউ কেউ ভুলে দুবার নাম লিখেছে। যেহেতু সাজানো, একই নাম সবসময় পরপর থাকবে। তুমি লাইন ধরে নামছ, আর যখনই দেখছ পরের নামটা এখনকার নামের মতোই — সেটা কেটে দিচ্ছ। পুরো লিস্ট তন্ন তন্ন করে খুঁজতে হচ্ছে না।

7. Visual explanation¶

cur দিয়ে হাঁটি; পরেরটা সমান হলে বাইপাস, নাহলে এগোই। 1->1->2->3->3:

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

8. Example input and output¶

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

9. Brute force thinking¶

sorted-এর সুবিধা ভুলে গিয়ে সরল চিন্তা: প্রতিটা node-এর জন্য বাকি পুরো list ঘুরে দেখো একই value আবার আছে কিনা, থাকলে সরাও। অথবা একটা set রাখো — value আগে দেখলে node বাদ।

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 এক জায়গায় বসেই সাফ হয়।

14. Step-by-step dry run¶

Input 1 -> 1 -> 2:

cur=1 (প্রথম), cur.next=1 (দ্বিতীয়): সমান → cur.next = 2 (প্রথম 1-এর arrow এখন 2-তে)। cur নড়ে না।
cur=1, cur.next=2: আলাদা → cur = 2
cur=2, cur.next=None: loop শেষ
return head = 1 -> 2

15. Python solution¶

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 অপরিবর্তিত।

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!।

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/দুই-লুপ লাগবে)।

21. Which basic problem this inherits from¶

ভিত্তি: traversal + delete-after-node (../operations.md-এর delete অংশ; ../implementation.py-তে node-বাইপাস দেখো)। sorted-adjacency কৌশল ../patterns.md-তে।

22. Similar harder problems¶

Remove Duplicates from Sorted List II (সব ডুপ্লিকেট একদম মুছে দাও) — https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
Remove Linked List Elements (value ধরে মুছা) — https://leetcode.com/problems/remove-linked-list-elements/ (এই tracker-এর #6)
Merge Two Sorted Lists (sorted-adjacency কাজে লাগানো) — https://leetcode.com/problems/merge-two-sorted-lists/ (#2)

23. Pattern learned¶

Pointer rewiring on a sorted list: sorted বলে সমান value পাশাপাশি; পাশের node তুলনা করে arrow ঘুরিয়ে এক পাসে ডুপ্লিকেট সাফ — set ছাড়াই O(1) space।

24. Final summary¶

ভবিষ্যতের আমাকে: "sorted list-এ ডুপ্লিকেট? পাশের node দেখো, সমান হলে বাইপাস, cur নড়িও না।" sorted = adjacency — এই একটা শব্দই set বাঁচিয়ে দেয়। unsorted হলে কিন্তু আলাদা গল্প।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।