007 — Delete Node in a Linked List

Problem link ও উৎস

• 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, কিন্তু উল্টো দিক থেকে

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

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

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

উদাহরণ

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

Input ও 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 সবসময় আছে)।

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

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

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

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

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

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

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

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

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

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

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

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

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

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

উদাহরণ

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

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

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

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

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

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

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

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

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

ছবিতে বোঝা

হাতে 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

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

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

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

Python

Python

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

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

• 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 দিয়েই ফল মাপি।

Output মিলিয়ে দেখা

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

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

সময়

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

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

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

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

• 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 বদলায় না।

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

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

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

পরের অনুশীলন

• Remove Linked List Elements (head থাকা স্বাভাবিক delete) — https://leetcode.com/problems/remove-linked-list-elements/ (এই tracker-এর #6)
• Remove Nth Node From End of List (runner দিয়ে আগের node ধরা) — https://leetcode.com/problems/remove-nth-node-from-end-of-list/ (#9)
• Delete the Middle Node of a Linked List — https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/

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

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

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

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

---

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