Problem link ও উৎস
- **Original source:** Classic linked list exercise
- **Platform:** LeetCode —
- **Topic:** linked list
- **Difficulty:** Medium
- **Pattern:** dummy head + carry
- **Basic idea inherited from:** merge skeleton (problem 2) + স্কুলের হাতে-যোগ (math fundamentals)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
দুটো সংখ্যা দুটো linked list হিসেবে দেওয়া, কিন্তু digit গুলো **উল্টো** করে রাখা — মানে একক স্থানের digit সবার আগে। দুটো সংখ্যা যোগ করে ফলটাও একই রকম উল্টো-digit list হিসেবে return করো।
```text
342 লেখা আছে : 2 -> 4 -> 3 (একক আগে: 2, তারপর 4, তারপর 3)
465 লেখা আছে : 5 -> 6 -> 4
342 + 465 = 807
ফল : 7 -> 0 -> 8
```
### Input ও output {#8-example-input-and-output}
```text
Input : l1 = 2 -> 4 -> 3 , l2 = 5 -> 6 -> 4 -> Output: 7 -> 0 -> 8 (342+465=807)
Edge 1 (শেষে carry বাকি): l1 = 9 -> 9 , l2 = 1 -> Output: 0 -> 0 -> 1 (99+1=100)
Edge 2 (অসমান দৈর্ঘ্য) : l1 = 0 , l2 = 0 -> Output: 0
Edge 3 (একটা লম্বা) : l1 = 5 , l2 = 5 -> Output: 0 -> 1 (5+5=10)
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
হাতে কলমে দুটো সংখ্যা যোগ করার মতো — ডান দিক (একক) থেকে শুরু করো, প্রতি কলামে যোগ করো, ১০ বা তার বেশি হলে নিচে এক ঘরের digit লেখো আর "এক হাতে" পরের কলামে নিয়ে যাও। list-এর উল্টো-digit মানে তুমি এমনিতেই ডান দিক থেকে শুরু করছ।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
দুটো জিনিস জোড়া লাগছে। প্রথমত problem 2 ([[002-merge-two-sorted-lists.md](002-merge-two-sorted-lists.md)](002-merge-two-sorted-lists.md))-এর **dummy + tail** কাঠামো — দুটো list একসাথে হেঁটে নতুন list বানানো। দ্বিতীয়ত স্কুলে শেখা **হাতে-যোগ**: ডান থেকে digit যোগ করো, ১০ পেরোলে "হাতে এক" (carry) পরের ঘরে নাও। digit উল্টো থাকায় list-এর শুরু থেকেই হাঁটা মানে একক স্থান থেকে শুরু — যোগের জন্য একদম উপযুক্ত।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো অঙ্ক positional addition। প্রতি ঘরে: `sum = d1 + d2 + carry`; নতুন digit হলো `sum % 10`, আর পরের ঘরের carry হলো `sum // 10`। Python-এ `divmod(sum, 10)` একবারে `(carry, digit)` দিয়ে দেয়। উল্টো-digit রাখায় index অনুযায়ী জায়গা মেলানো লাগে না — দুই list সমানতালে এগোলেই হয়।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **dummy head** + একটা `tail` pointer (ফল গাঁথতে), আর একটা `carry` সংখ্যা। নতুন প্রতিটা digit-এর জন্য নতুন node বানিয়ে `tail`-এ জুড়ি।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
Linked list-এ শেষে node জোড়া O(1) (tail ধরে রাখলে), আর দৈর্ঘ্য আগে জানার দরকার নেই — যোগ যতদূর গড়ায় ততদূর জোড়া যায়। dummy head থাকায় ফল-list-এর প্রথম node নিয়ে আলাদা ভাবতে হয় না; carry শেষ পর্যন্ত থাকলে এক ঘর বেড়ে যাওয়া সংখ্যাও (যেমন 99 + 1 = 100) সহজে ধরা পড়ে।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
সরল চিন্তা: দুই list-কে আলাদা করে পূর্ণ সংখ্যায় রূপান্তর করো (digit গুলো বসিয়ে), Python-এ যোগ করো, তারপর ফলের digit গুলো আবার উল্টো করে list বানাও।
```text
2->4->3 => 342
5->6->4 => 465
342 + 465 = 807
807 => 7 -> 0 -> 8
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
এটা ছোট input-এ কাজ করে, কিন্তু সংখ্যা বিশাল হলে (হাজার হাজার digit) পুরো সংখ্যা বানিয়ে যোগ করা ভঙ্গুর ও অপচয় — অনেক ভাষায় তো বড় সংখ্যাই ধরবে না। ঘরে-ঘরে carry পদ্ধতি কোনো বড় সংখ্যা না বানিয়ে এক পাসেই কাজ সারে, যেকোনো দৈর্ঘ্যে।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: পুরো সংখ্যা বানানোর দরকার **নেই**। প্রতিটা ঘর স্বাধীনভাবে যোগ করা যায়, শুধু এক ঘরের carry পরের ঘরে নিয়ে গেলেই হয়। উল্টো-digit থাকায় দুই list সমানে এগোলেই ঘর গুলো মিলে যায়।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
dummy + tail বানাও, `carry = 0` রাখো। যতক্ষণ `l1` বা `l2`-এ node আছে **অথবা** carry বাকি আছে: দুই (থাকলে) digit আর carry যোগ করো, `divmod(sum, 10)` দিয়ে নতুন carry ও digit বের করো, digit-এর node tail-এ জুড়ো, দুই list (থাকলে) এগোও। শেষে `dummy.next`।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "দুটো সংখ্যা যোগ" না ভেবে ভাবো — "দুটো digit-স্রোত একসাথে হাঁটাই, প্রতি ঘরে যোগ + হাতে-এক বহন করি।" loop শর্তে `carry`-কেও রাখলে শেষের অতিরিক্ত digit (100-এর সেই 1) আপনাআপনি ধরা পড়ে।
### ছবিতে বোঝা {#7-visual-explanation}
`carry` সহ ঘরে ঘরে যোগ। `2->4->3` (342) আর `5->6->4` (465):
```text
ঘর 1: 2 + 5 + carry(0) = 7 → digit 7, carry 0 ফল: 7
ঘর 2: 4 + 6 + carry(0) = 10 → digit 0, carry 1 ফল: 7 -> 0
ঘর 3: 3 + 4 + carry(1) = 8 → digit 8, carry 0 ফল: 7 -> 0 -> 8
দুই list শেষ, carry 0 → থামো
return: 7 -> 0 -> 8 (= 807)
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `l1 = 9 -> 9`, `l2 = 1` (99 + 1 = 100):
1. `dummy`, `tail = dummy`, `carry = 0`
2. ঘর 1: `9 + 1 + 0 = 10` → `divmod(10,10) = (1, 0)` → node 0; `carry = 1`; `l1 = 9`, `l2 = None`
3. ঘর 2: `9 + 0 + 1 = 10` → `(1, 0)` → node 0; `carry = 1`; `l1 = None`
4. ঘর 3: `l1`/`l2` শেষ, কিন্তু `carry = 1` → `0 + 0 + 1 = 1` → `(0, 1)` → node 1; `carry = 0`
5. সব শেষ, carry 0 → থামো; return `dummy.next` = `0 -> 0 -> 1` (= 100)
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def add_two_numbers(l1, l2):
dummy = ListNode() # নকল head — ফলের প্রথম node-এর special case এড়াতে
tail = dummy
carry = 0
while l1 or l2 or carry: # carry-ও শর্তে: শেষের অতিরিক্ত digit ধরতে
s = carry
if l1:
s += l1.val
l1 = l1.next
if l2:
s += l2.val
l2 = l2.next
carry, digit = divmod(s, 10) # (হাতে-এক, এই ঘরের digit)
tail.next = ListNode(digit)
tail = tail.next
return dummy.next
# ---- 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(add_two_numbers(build([2, 4, 3]), build([5, 6, 4]))) == [7, 0, 8] # 342+465
assert to_list(add_two_numbers(build([9, 9]), build([1]))) == [0, 0, 1] # 99+1
assert to_list(add_two_numbers(build([0]), build([0]))) == [0] # 0+0
assert to_list(add_two_numbers(build([5]), build([5]))) == [0, 1] # 5+5=10
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `dummy = ListNode()` — নকল head, ফল-list সহজে গাঁথতে।
- `tail = dummy` — `tail` সবসময় ফল-list-এর শেষে।
- `carry = 0` — শুরুতে হাতে কিছু নেই।
- `while l1 or l2 or carry:` — যেকোনো list বাকি থাকলে, বা carry বাকি থাকলে চলবে।
- `s = carry` তারপর `if l1: ... if l2: ...` — যেটা যেটা আছে যোগ করো, সেই list এগোও।
- `carry, digit = divmod(s, 10)` — পরের carry আর এই ঘরের digit একসাথে।
- `tail.next = ListNode(digit); tail = tail.next` — নতুন digit-node জুড়ে tail এগোও।
- `return dummy.next` — ফলের আসল head।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`[2,4,3]` + `[5,6,4]` ঘরে-ঘরে 7,0,8 দেয় → `[7,0,8]`। `[9,9]` + `[1]`-এ carry শেষ পর্যন্ত গড়িয়ে `[0,0,1]`। `[0]` + `[0]` → `[0]`। `[5]` + `[5]`-এ 10 → `[0,1]`। সব assert pass → `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(max(n, m))** — n, m দুই list-এর দৈর্ঘ্য; লম্বাটার প্রতিটা ঘর একবার করে process হয় (+ সম্ভবত একটা অতিরিক্ত carry ঘর)।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(max(n, m))** — ফল-list-এ ততগুলো নতুন node বানে; pointer ছাড়া অন্য কোনো বড় structure নেই। (output বাদ দিলে auxiliary O(1)।)
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- loop শর্তে `carry` রাখতে ভুলে যাওয়া — তখন শেষের অতিরিক্ত digit (যেমন 100-এর 1) হারিয়ে যায়।
- `l1`/`l2` None কিনা না দেখে `.val` পড়া — অসমান দৈর্ঘ্যে crash।
- carry আর digit উল্টে নেওয়া (`digit, carry = divmod(...)`) — `divmod` ফেরায় `(ভাগফল, ভাগশেষ)`, তাই `carry` আগে।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: problem 2 ([[002-merge-two-sorted-lists.md](002-merge-two-sorted-lists.md)](002-merge-two-sorted-lists.md))-এর dummy + tail দিয়ে দুই list একসাথে হাঁটার skeleton; সাথে স্কুলের positional addition (math fundamentals)।
### পরের অনুশীলন {#22-similar-harder-problems}
- Add Two Numbers II (digit সোজা ক্রমে, stack/reverse লাগে) —