Skip to content

007 — Delete Node in a Linked List

Source

  • Original source: Classic linked list 'trick' exercise
  • Platform: LeetCode — https://leetcode.com/problems/delete-node-in-a-linked-list/
  • Topic: linked list
  • Difficulty: Easy (একটা 'trick' problem)
  • Pattern: value-copy trick
  • Basic idea inherited from: bypass-deletion, কিন্তু উল্টো দিক থেকে

1. Problem in simple words

মজার ব্যাপারটা এখানে: তোমাকে list-এর head দেওয়া হয়নি। তোমাকে শুধু একটা node-ই হাতে ধরিয়ে দেওয়া হয়েছে — সেই node-টাকেই list থেকে মুছতে হবে। নিশ্চয়তা: এই node কখনো শেষ (tail) node হবে না, মানে এর একটা next সবসময় আছে।

list: 4 -> 5 -> 1 -> 9
দেওয়া হলো: node (val=5)
মুছার পরে: 4 -> 1 -> 9

2. Which basic idea does this inherit from?

ভিত্তি সেই চেনা bypass-deletion — "আগের node-এর arrow পরেরটার দিকে ঘুরিয়ে দাও।" কিন্তু এখানে মোচড়: আমরা আগের node-এ পৌঁছাতেই পারি না (head নেই, তাই পিছনে হাঁটা অসম্ভব)। তাই idea-টা উল্টো করে খাটাতে হয় — এই node-কে delete না করে, পরের node-কে delete করি, আর এই node-কে পরেরটার নকল বানিয়ে দিই।

3. What is the hidden math or logic?

লুকানো logic: একটা node "কে" তা আসলে তার value + পরের দিকের arrow দিয়েই সংজ্ঞায়িত — আগের কেউ তাকে চেনে না, শুধু "যে এখানে আসে" সে চেনে। তাই যদি এই node-এর ভেতরে পরের node-এর value ঢেলে দিই আর পরেরটাকে বাইপাস করি, তাহলে বাইরের কেউ পার্থক্য বুঝবে না — কার্যত এই node-টাই "মুছে গেছে" বলে মনে হবে।

4. Which data structure is needed?

কোনো extra structure লাগে না — শুধু হাতে পাওয়া node আর তার node.next। দুটো assignment-ই যথেষ্ট। O(1) time, O(1) space।

5. Why this data structure fits

Linked list-এ একটা node-কে "মুছা" মানে আসলে তাকে chain থেকে লুকিয়ে ফেলা। সাধারণত আগের node-এর arrow ঘুরিয়ে লুকাই। আগের node নাগালের বাইরে বলে, আমরা সুবিধাটা নিই যে node-এর value লেখা যায়: পরের node-এর তথ্য (value ও next) এই node-এ copy করে, পরেরটাকে chain থেকে বাদ দিই। arrow আর value লেখা — দুটোই O(1), তাই perfect fit।

6. Real-life analogy

একটা সারিতে চেয়ারে নাম-ফলক বসানো লোক বসে আছে, তুমি শুধু একজনের সামনে দাঁড়িয়ে — সারির শুরু কোথায় জানো না, তাই পিছনের লোকের কাছে যেতে পারছ না। সামনের লোককে সরাতে হবে। কৌশল: তুমি তোমার সামনের লোকের নাম-ফলক ও পরিচয় এই লোকের গায়ে বসিয়ে দিলে, আর আসল সামনের লোককে সারি থেকে উঠিয়ে দিলে। বাইরে থেকে দেখে মনে হবে এই লোকটাই চলে গেছে।

7. Visual explanation

হাতে node(val=5); 4 -> 5 -> 1 -> 9:

শুরু:               4 -> [5] -> 1 -> 9        ([] = হাতে পাওয়া node)

ধাপ 1: value copy   node.val = node.next.val (1)
                    4 -> [1] -> 1 -> 9

ধাপ 2: bypass next  node.next = node.next.next (9)
                    4 -> [1] -> 9
                              ↑ পুরোনো '1' node chain থেকে বাদ

ফল:                 4 -> 1 -> 9

8. Example input and output

list: 4 -> 5 -> 1 -> 9 ; দেওয়া node = (5)   -> ফল: 4 -> 1 -> 9
list: 4 -> 5 -> 1 -> 9 ; দেওয়া node = (1)   -> ফল: 4 -> 5 -> 9

মনে রাখো: দেওয়া node কখনো tail নয় (তাই node.next সবসময় আছে)।

9. Brute force thinking

স্বাভাবিক delete-এর সরল চিন্তা: head থেকে হেঁটে দেওয়া node-এর ঠিক আগের node খুঁজি, তারপর prev.next = node.next করে বাইপাস করি।

prev খুঁজি যার prev.next == node
prev.next = node.next

10. Why brute force is slow

এই সমাধান এখানে চালানোই যায় না — কারণ head দেওয়া হয়নি, তাই prev খোঁজার মতো শুরুর বিন্দুই নেই। singly linked list-এ পিছনের দিকে যাওয়া অসম্ভব। তাই "আগের node বের করে বাইপাস" পথটা এখানে বন্ধ; নতুন করে ভাবতে হবে।

11. Key observation

মূল observation: কোনো node-কে delete করার আসল লক্ষ্য তো তার content (value) chain থেকে সরানো — ঠিক ওই memory-র object-টা সরানো জরুরি নয়। তাই এই node-এ পরেরটার value বসিয়ে, পরের node-টাকে বাদ দিলেই কাজ হাসিল।

12. Optimized intuition

দুই লাইনেই শেষ: প্রথমে node.val = node.next.val — পরের node-এর value এই node-এ copy করো। তারপর node.next = node.next.next — পরের node-কে chain থেকে বাইপাস করো। এখন এই node দেখতে-শুনতে পরের node-এর মতো, আর আসল পরের node হারিয়ে গেছে — কার্যত যেটা মুছতে বলা হয়েছিল, সেটাই মুছল।

13. Thinking tweak

মোচড়: "এই node-টা মুছব" — এটাই ভুল লক্ষ্য। বদলে ভাবো "এই node-টাকে পরেরটার নকল বানিয়ে, পরেরটাকে মুছব।" আগের দিকে যেতে পারছ না? তাহলে সামনের দিকে এক ঘর সরিয়ে delete-টা করো — দিক উল্টে দাও।

14. Step-by-step dry run

list 4 -> 5 -> 1 -> 9, হাতে পাওয়া node = val 5-ওয়ালা node:

  1. শুরু: node.val = 5, node.next = (val 1)
  2. node.val = node.next.val → node.val = 1; এখন list 4 -> 1 -> 1 -> 9 (হাতের node-এ 1 বসল)
  3. node.next = node.next.next → node.next = (val 9); পুরোনো 1 node বাইপাস
  4. ফল list: 4 -> 1 -> 9

15. Python solution

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def delete_node(node):
    node.val = node.next.val        # পরের node-এর value এখানে copy করো
    node.next = node.next.next      # পরের node-কে বাইপাস করো (কার্যত self delete)

# ---- 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

def node_at(head, idx):
    cur = head
    for _ in range(idx):           # idx ঘর এগিয়ে target node-এ পৌঁছাও
        cur = cur.next
    return cur

# ---- tests ----
head = build([4, 5, 1, 9])
delete_node(node_at(head, 1))      # index 1 = val 5 মুছে দাও
assert to_list(head) == [4, 1, 9]

head = build([4, 5, 1, 9])
delete_node(node_at(head, 2))      # index 2 = val 1 মুছে দাও
assert to_list(head) == [4, 5, 9]
print("সব test pass!")

16. Line-by-line code explanation

  • def delete_node(node): — head নয়, শুধু মুছতে-হওয়া node-টাই argument।
  • node.val = node.next.val — পরের node-এর value এই node-এ লিখে ফেলি; এখন এই node "পরেরটার মতো"।
  • node.next = node.next.next — পরের (আসল) node-কে chain থেকে বাদ দিই; তার আর কোনো রেফারেন্স রইল না।
  • node_at(head, idx) — test-এর জন্য: head থেকে idx ঘর এগিয়ে target node-এর রেফারেন্স ধরে আনে।
  • দুটো test-এ আলাদা index-এর node দিয়ে delete যাচাই, in-place mutation বলে head দিয়েই ফল মাপি।

17. Output walkthrough

build([4,5,1,9]) বানায় 4->5->1->9। node_at(head,1) দেয় val 5-এর node; delete_node সেটায় 1 বসিয়ে পরের 1-node বাদ দেয় → [4,1,9]। নতুন list-এ node_at(head,2) দেয় val 1-এর node; delete করলে → [4,5,9]। সব assert pass → সব test pass!।

18. Time complexity

O(1) — মাত্র দুটো assignment; list-এর দৈর্ঘ্যের উপর নির্ভর করে না।

19. Space complexity

O(1) — কোনো extra structure নেই; শুধু in-place লেখা।

20. Common mistakes

  • tail node মুছতে চাওয়া — node.next তখন None, node.next.val-এ crash; problem-এর শর্তই বলে দেওয়া node tail নয়।
  • শুধু node.val = node.next.val করে node.next ঘোরাতে ভুলে যাওয়া — তখন value ঠিক হলেও duplicate node থেকে যায়।
  • node = node.next করে ভাবা delete হয়ে গেছে — এটা শুধু local pointer সরায়, আসল chain বদলায় না।

21. Which basic problem this inherits from

ভিত্তি: bypass-deletion (../operations.md-এর delete অংশ), কিন্তু আগের node নাগালে নেই বলে উল্টো করে প্রয়োগ। arrow-rewiring শৃঙ্খলার ছবি ../visual-explanation.md-তে। স্বাভাবিক value-ধরা delete-এর জন্য দেখো 006-remove-elements.md।

22. Similar harder problems

23. Pattern learned

Value-copy trick: আগের node-এ পৌঁছানো না গেলে, এই node-এ পরেরটার value copy করে পরেরটাকে বাইপাস করো — "এই node delete"-কে "পরের node delete"-এ রূপান্তর।

24. Final summary

ভবিষ্যতের আমাকে: "শুধু node দেওয়া, head নেই? আগের দিকে যেতে পারবে না — তাই এই node-এ পরেরটার value ঢেলে পরেরটাকে মুছে দাও।" delete-এর দিক উল্টে দেওয়াই এই trick-এর প্রাণ; tail হলে কিন্তু খাটবে না।

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