Skip to content

006 — Remove Linked List Elements

Source

  • Original source: Classic linked list exercise
  • Platform: LeetCode — https://leetcode.com/problems/remove-linked-list-elements/
  • Topic: linked list
  • Difficulty: Easy
  • Pattern: dummy head
  • Basic idea inherited from: delete-by-value + dummy head head-deletion-কে un-special বানায়

1. Problem in simple words

একটা linked list আর একটা সংখ্যা val দেওয়া। list-এর মধ্যে যত node-এর value ঠিক val-এর সমান, সব সরিয়ে দাও — সেটা list-এর মাঝে থাকুক, শেষে থাকুক, এমনকি একদম প্রথমে (head) থাকুক। নতুন head return করো।

val = 6
আগে : 1 -> 2 -> 6 -> 3 -> 4 -> 5 -> 6
পরে : 1 -> 2 -> 3 -> 4 -> 5

2. Which basic idea does this inherit from?

ভিত্তি delete-by-value — value মিললে node বাইপাস করা। কিন্তু একটা ঝামেলা আছে: যদি head নিজেই মুছতে হয়? তখন head বদলে যায়, আলাদা করে সামলাতে হয়। এর সমাধান problem 2 (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 বিশেষ শাখা লাগে না।

6. Real-life analogy

একটা ট্রেনের বগি সারি থেকে নষ্ট বগিগুলো খুলে ফেলছ। মাঝের বগি খুলতে সহজ — সামনের বগিকে পরেরটার সাথে জুড়ে দাও। কিন্তু ইঞ্জিনের ঠিক পরের বগিটা নষ্ট হলে? তখন "সামনের বগি" বলে কিছু নেই। সমাধান: ইঞ্জিনের আগে একটা ডামি কাপলিং (dummy) লাগিয়ে দাও — এখন প্রথম বগিরও একটা "আগের" অংশ আছে, সব বগি একইভাবে খোলা যায়।

7. Visual explanation

dummy head-এর আগে; prev রাখা-অংশের শেষে, cur যাচাই করছে। val=6, list 6->1->6:

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

8. Example input and output

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

9. Brute force thinking

dummy head ছাড়া সরল চিন্তা: প্রথমে একটা while-loop দিয়ে শুরুর দিকের সব val-node সরাও (head বারবার এগিয়ে দাও); তারপর আরেকটা loop দিয়ে বাকি list-এর মাঝের node গুলো বাইপাস করো।

ধাপ 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-কে সাধারণ বানিয়ে ফেলা।

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

15. Python solution

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 এখানে।

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

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।

21. Which basic problem this inherits from

ভিত্তি: delete-by-value (../operations.md) + dummy-head কৌশল, যেটা problem 2-এ প্রথম এসেছিল (002-merge-two-sorted-lists.md)। dummy-head-এর সাধারণ ব্যাখ্যা ../patterns.md-তে।

22. Similar harder problems

23. Pattern learned

Dummy head: আসল head-এর আগে একটা নকল node বসিয়ে head-deletion/insertion-কে সাধারণ case বানানো; শেষে dummy.next ফেরত দিয়ে আসল head পাওয়া।

24. Final summary

ভবিষ্যতের আমাকে: "head নিজেই মুছতে/বদলাতে পারে এমন যেকোনো problem-এ — আগে একটা dummy head বসাও।" তাহলে edge case হাওয়া, একটাই পরিষ্কার loop, শেষে dummy.next। delete, insert, merge — সবেতেই এই বন্ধু।

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