Problem link ও উৎস
- **Original source:** Classic linked list 'trick' exercise
- **Platform:** LeetCode —
- **Topic:** linked list
- **Difficulty:** Easy (একটা 'trick' problem)
- **Pattern:** value-copy trick
- **Basic idea inherited from:** bypass-deletion, কিন্তু উল্টো দিক থেকে
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
মজার ব্যাপারটা এখানে: তোমাকে list-এর head **দেওয়া হয়নি**। তোমাকে শুধু একটা node-ই হাতে ধরিয়ে দেওয়া হয়েছে — সেই node-টাকেই list থেকে মুছতে হবে। নিশ্চয়তা: এই node কখনো **শেষ (tail) node হবে না**, মানে এর একটা `next` সবসময় আছে।
```text
list: 4 -> 5 -> 1 -> 9
দেওয়া হলো: node (val=5)
মুছার পরে: 4 -> 1 -> 9
```
### Input ও output {#8-example-input-and-output}
```text
list: 4 -> 5 -> 1 -> 9 ; দেওয়া node = (5) -> ফল: 4 -> 1 -> 9
list: 4 -> 5 -> 1 -> 9 ; দেওয়া node = (1) -> ফল: 4 -> 5 -> 9
মনে রাখো: দেওয়া node কখনো tail নয় (তাই node.next সবসময় আছে)।
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
একটা সারিতে চেয়ারে নাম-ফলক বসানো লোক বসে আছে, তুমি শুধু একজনের সামনে দাঁড়িয়ে — সারির শুরু কোথায় জানো না, তাই পিছনের লোকের কাছে যেতে পারছ না। সামনের লোককে সরাতে হবে। কৌশল: তুমি **তোমার সামনের** লোকের নাম-ফলক ও পরিচয় এই লোকের গায়ে বসিয়ে দিলে, আর আসল সামনের লোককে সারি থেকে উঠিয়ে দিলে। বাইরে থেকে দেখে মনে হবে এই লোকটাই চলে গেছে।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#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।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
স্বাভাবিক delete-এর সরল চিন্তা: head থেকে হেঁটে দেওয়া node-এর **ঠিক আগের** node খুঁজি, তারপর `prev.next = node.next` করে বাইপাস করি।
```text
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-টা করো — দিক উল্টে দাও।
### ছবিতে বোঝা {#7-visual-explanation}
হাতে `node`(val=5); `4 -> 5 -> 1 -> 9`:
```text
শুরু: 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-এ ধাপে ধাপে {#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`
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```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!")
```
### কোডের প্রতিটি অংশ {#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 দিয়েই ফল মাপি।
### Output মিলিয়ে দেখা {#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!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#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 বদলায় না।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: bypass-deletion ([../operations.md](../operations.md)-এর delete অংশ), কিন্তু আগের node নাগালে নেই বলে **উল্টো করে** প্রয়োগ। arrow-rewiring শৃঙ্খলার ছবি [../visual-explanation.md](../visual-explanation.md)-তে। স্বাভাবিক value-ধরা delete-এর জন্য দেখো [[006-remove-elements.md](006-remove-elements.md)](006-remove-elements.md)।
### পরের অনুশীলন {#22-similar-harder-problems}
- Remove Linked List Elements (head থাকা স্বাভাবিক delete) —