কনটেন্টে যান

005 — Remove Duplicates from Sorted List

Problem link ও উৎস

প্রশ্ন ও উদাহরণ

সহজ করে প্রশ্ন

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

উদাহরণ
আগে : 1 -> 1 -> 2 -> 3 -> 3
পরে : 1 -> 2 -> 3

Input ও 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

চেনা উদাহরণে বোঝা

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

ভিত্তির ধারণা

আগের কোন ধারণাটি লাগবে

ভিত্তি দুটো: সাধারণ traversal (list ধরে হাঁটা) আর delete-after-node operation — মানে "একটা node-এর পরেরটা বাইপাস করে দাও।" topic-এর ../operations.md-এ এই বাইপাস-delete-এর মূল ছবি আছে; এখানে সেটাই বারবার লাগাই।

ভেতরের যুক্তি

লুকানো logic হলো sorted মানে সমান value পাশাপাশি। তাই কোনো value আবার আছে কিনা খুঁজতে পুরো list চষতে হয় না — শুধু ঠিক পরের node-টা দেখলেই হয়। এই adjacency property-ই পুরো problem-টা O(n)-এ নামিয়ে দেয়।

কী দিয়ে তথ্য রাখব

কোনো extra data structure লাগে না — শুধু একটা pointer (cur)। sorted বলে hash set-এ "আগে দেখেছি কিনা" রাখার দরকার নেই; পাশের node-ই যথেষ্ট। O(1) extra space।

এটি কেন উপযুক্ত

Linked list-এ একটা node সরানো মানে শুধু একটা arrow ঘোরানো (cur.next = cur.next.next) — O(1)। যেহেতু ডুপ্লিকেট পাশাপাশি, আমরা cur আর cur.next-এর value তুলনা করে সাথে সাথে সিদ্ধান্ত নিতে পারি। কোনো খোঁজাখুঁজি নেই, কোনো বাড়তি memory নেই।

ধাপে ধাপে সমাধান

প্রথম সরল উপায়

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

উদাহরণ
set = {}
1 দেখলাম -> রাখো, set={1}
1 আবার   -> set-এ আছে -> বাদ
2 দেখলাম -> রাখো, set={1,2}
...

কোথায় বেশি কাজ হচ্ছে

প্রতিটা node-এর জন্য বাকি list খুঁজলে O(n^2) হয়ে যায়। set ব্যবহার করলে সময় O(n) ঠিকই, কিন্তু O(n) extra space লাগে — যেটা পুরো অপ্রয়োজনীয়, কারণ list তো already sorted। sorted অবস্থা কাজে লাগালে set ছাড়াই, পাশের node দেখেই O(n) সময় + O(1) space-এ হয়।

যে বিষয়টি খেয়াল করতে হবে

মূল observation: list sorted, তাই সমান value সবসময় পাশাপাশি। সুতরাং কোনো node ডুপ্লিকেট কিনা জানতে শুধু তার ঠিক পরের node-টা দেখলেই চলে — অতীত মনে রাখার (set) দরকার নেই।

আরও কম কাজে সমাধান

cur কে head থেকে চালাও। প্রতি ধাপে cur.val আর cur.next.val তুলনা করো। সমান হলে পরের node বাইপাস করো (cur.next = cur.next.next) — cur নড়াও না, কারণ আরও ডুপ্লিকেট থাকতে পারে। আলাদা হলে cur এক ঘর এগোও। শেষে আসল head ফেরত দাও।

ভাবনার পরিবর্তন

মোচড়: "কোন কোন value আগে দেখেছি" মনে রাখার বদলে — যেহেতু সাজানো, শুধু "পরেরটা কি আমার মতোই?" জিজ্ঞেস করো। স্মৃতির জায়গায় প্রতিবেশী। আর সমান পেলে cur না নড়িয়ে রাখো, যাতে টানা ডুপ্লিকেটের পুরো run এক জায়গায় বসেই সাফ হয়।

ছবিতে বোঝা

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

ছোট input-এ ধাপে ধাপে

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

কোড ও ব্যাখ্যা

Python

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!")

কোডের প্রতিটি অংশ

  • 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 মিলিয়ে দেখা

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

খরচ ও সাধারণ ভুল

সময়

O(n) — প্রতিটা node ঠিক একবার করে দেখা হয়; তুলনা ও বাইপাস দুটোই O(1)।

অতিরিক্ত জায়গা

O(1) — শুধু একটা pointer; sorted বলে hash set-এর O(n) লাগে না।

যে ভুলগুলো এড়াতে হবে

  • সমান পেয়ে cur এগিয়ে দেওয়া — তখন টানা তিন বা ততোধিক সমান value-তে একটা ডুপ্লিকেট থেকে যায়। সমান হলে cur স্থির রাখো।
  • while শর্তে cur.next ভুলে শুধু cur রাখা — cur.next.val-এ crash।
  • এটা sorted-নির্ভর; unsorted list-এ এই পদ্ধতি কাজ করবে না (তখন set/দুই-লুপ লাগবে)।

শেখা ও পরের অনুশীলন

ভিত্তির সঙ্গে সম্পর্ক

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

পরের অনুশীলন

কৌশলটি মনে রাখুন

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

নিজেকে যাচাই করুন

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

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