Problem link ও উৎস
- **Original source:** Classic capstone interview problem (the merge step of merge sort, on lists)
- **Platform:** LeetCode —
- **Topic:** linked lists + sorting
- **Difficulty:** Easy
- **Pattern:** Two-pointer merge with a dummy head
- **Basic idea inherited from:** এটা একটা cross-topic capstone — এখানে মেশে **03 linked lists** (node-এর `next` pointer জোড়া দিয়ে list গড়া, dummy head trick) আর **sorting ideas** (merge sort-এর "merge" ধাপ: দুটো sorted sequence-কে একটা sorted sequence-এ জোড়া)। দুই tool জোড়া লাগলেই এই problem।
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
তোমাকে দুটো **already sorted** (ছোট থেকে বড়) singly linked list দেওয়া আছে। তোমার কাজ: এদের জোড়া দিয়ে একটা নতুন sorted list বানাও, যেখানে দুটো list-এর সব node আছে, এখনও ছোট-থেকে-বড় সাজানো। নতুন list-এর head return করো — পুরনো node গুলোই কাজে লাগাও, value copy কোরো না।
```text
list1 : 1 -> 2 -> 4
list2 : 1 -> 3 -> 4
merged: 1 -> 1 -> 2 -> 3 -> 4 -> 4
```
### Input ও output {#8-example-input-and-output}
```text
Input : list1 = 1 -> 2 -> 4 , list2 = 1 -> 3 -> 4
Output: 1 -> 1 -> 2 -> 3 -> 4 -> 4
Edge case 1 (একটা খালি): list1 = None, list2 = 0 -> Output: 0
Edge case 2 (দুটোই খালি): list1 = None, list2 = None -> Output: None
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো দুজন বন্ধু আলাদা আলাদা ভাবে কম-থেকে-বেশি দামে সাজানো বইয়ের দুটো স্তূপ নিয়ে এসেছে। তুমি একটা নতুন তাক ভরছ। প্রতিবার দুই স্তূপের **উপরের দুটো বই**-এর মধ্যে যেটা সস্তা, সেটা তুলে তাকে রাখো। একটা স্তূপ শেষ হলে অন্যটা পুরোটা পেছনে জুড়ে দাও। তাকটা সাজানো থেকেই যায়।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এই problem দুটো আগের chapter-এর tool জোড়া দেয়:
- **03 linked lists** থেকে: একটা `dummy` head বানিয়ে তার পিছনে node জোড়া দেওয়া, আর একটা `tail` pointer দিয়ে শেষ প্রান্ত ধরে রাখা — list গড়ার ক্লাসিক কৌশল।
- **sorting ideas** থেকে: merge sort-এর হৃদয় হলো "merge": দুটো sorted run-এর সামনে দুটো আঙুল রেখে, প্রতিবার ছোটটা তুলে নেওয়া।
একা linked-list জ্ঞান দেয় pointer জোড়া দেওয়ার ক্ষমতা; একা merge-idea দেয় sorted রাখার কৌশল। দুটো মিললে O(m+n)।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic একটা **invariant**: দুটো list যেহেতু sorted, যেকোনো মুহূর্তে দুটো head-এর মধ্যে ছোটটাই হলো বাকি সব node-এর মধ্যে সবচেয়ে ছোট — তাই সেটা নির্দ্বিধায় merged list-এ পরের জায়গায় বসানো যায়। বারবার এই "দুই head-এর ছোটটা তোলো" করলেই output sorted থাকে।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
কোনো extra বড় structure লাগে না — শুধু একটা **dummy head node** আর একটা **tail pointer**, আর দুই input list-এ দুটো reading pointer (`a`, `b`)। dummy node (03 linked lists-এর trick) প্রথম node-এর special case ঝামেলা মুছে দেয়।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
Linked list-এ node গুলো আলাদা আলাদা memory-তে, শুধু `next` arrow দিয়ে বাঁধা। তাই array-র মতো সরাও-বসাও না করে, আমরা শুধু **arrow নতুন করে জুড়ে** দিই — `tail.next` কে ছোট node-এর দিকে তাক করাই। dummy head থাকায় "প্রথম node কোনটা" আলাদা করে ভাবতে হয় না; merge শেষে `dummy.next`-ই আসল head। এই কারণেই এটা নিখুঁত fit।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: দুটো list-এর সব value একটা array-তে ঢালো, array sort করো, তারপর নতুন list বানাও।
```text
1) দুই list -> [1,2,4,1,3,4]
2) sort -> [1,1,2,3,4,4]
3) array থেকে নতুন list গড়ো
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
এটা কাজ করে, কিন্তু **input যে already sorted সেই তথ্যটা ফেলে দেয়**। আবার sort করা মানে O((m+n) log(m+n)) সময় আর O(m+n) extra array। অথচ দুটো sorted list merge করতে শুধু O(m+n) লাগে আর কোনো নতুন node বানাতেই হয় না — পুরনো node-এর arrow ঘোরালেই হয় (two-way merge idea)।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **দুটো list sorted বলে, যেকোনো মুহূর্তে পরের সবচেয়ে ছোট element-টা অবশ্যই কোনো-না-কোনো list-এর বর্তমান head**। তাই পুরো জিনিস না দেখে, শুধু দুই head তুলনা করলেই পরের সঠিক node পেয়ে যাই। এটাই linear merge সম্ভব করে।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
একটা `dummy` head আর `tail` রাখো। দুই list-এর head `a`, `b` তুলনা করো; ছোটটাকে `tail.next`-এ জুড়ে সেই list-এ এক ঘর এগোও, `tail`-ও এগোও। একটা list শেষ হলে অন্যটার বাকি অংশ পুরোটা `tail.next`-এ ঝুলিয়ে দাও (যেহেতু সেটা নিজে sorted)। শেষে `dummy.next` return করো।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "merge করা" ভাবার বদলে ভাবো "দুই head-এর মধ্যে ছোটটা বেছে tail-এ সেলাই করি, একটা শেষ হলে বাকিটা ঝুলিয়ে দিই।" dummy head থাকায় প্রথম node-এর special case-ও মিলিয়ে যায়।
### ছবিতে বোঝা {#7-visual-explanation}
`a: 1->2->4`, `b: 1->3->4` merge করার tail-গড়া:
```text
dummy -> ? a=1 b=1
1<=1 -> tail.next=a(1) dummy->1 a=2 b=1
1< 2 -> tail.next=b(1) dummy->1->1 a=2 b=3
2< 3 -> tail.next=a(2) dummy->1->1->2 a=4 b=3
3< 4 -> tail.next=b(3) dummy->1->1->2->3 a=4 b=4
4<=4 -> tail.next=a(4) dummy->1->1->2->3->4 a=N b=4
b বাকি -> tail.next=b dummy->1->1->2->3->4->4 শেষ
head = dummy.next = 1->1->2->3->4->4
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `a: 1->3`, `b: 2`:
1. শুরু: `dummy`, `tail = dummy`, `a = 1`, `b = 2`
2. `1 <= 2` → `tail.next = a(1)`; `tail` এগোলো; `a = 3`
3. `3 > 2` → `tail.next = b(2)`; `tail` এগোলো; `b = None`
4. `b = None` → বাকি `a` (`3`) পুরোটা `tail.next`-এ ঝোলাও
5. return `dummy.next` = `1 -> 2 -> 3`
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def merge_two_lists(a, b):
dummy = ListNode() # special-case এড়াতে fake head
tail = dummy
while a and b:
if a.val <= b.val: # দুই head-এর ছোটটা তোলো
tail.next = a
a = a.next
else:
tail.next = b
b = b.next
tail = tail.next # tail এক ঘর এগোলো
tail.next = a if a else b # যেটা বাকি, পুরোটা ঝোলাও
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(merge_two_lists(build([1, 2, 4]), build([1, 3, 4]))) == [1, 1, 2, 3, 4, 4]
assert to_list(merge_two_lists(build([]), build([0]))) == [0] # একটা খালি
assert to_list(merge_two_lists(build([]), build([]))) == [] # দুটোই খালি
assert to_list(merge_two_lists(build([5]), build([1, 2, 3]))) == [1, 2, 3, 5]
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `dummy = ListNode()` — একটা fake head, যাতে প্রথম আসল node জোড়ার সময় special case না লাগে (03 linked lists trick)।
- `tail = dummy` — `tail` সবসময় merged list-এর শেষ node ধরে রাখে।
- `while a and b` — যতক্ষণ দুটো list-এই node আছে, তুলনা চালাও।
- `if a.val <= b.val` — `<=` রাখায় stable থাকে (সমান হলে `a` আগে); ছোটটা `tail.next`-এ জোড়।
- `tail = tail.next` — জোড়ার পর tail এক ঘর সামনে।
- `tail.next = a if a else b` — একটা list শেষ; বাকিটা যেহেতু নিজে sorted, পুরোটা একবারে ঝুলিয়ে দাও।
- `return dummy.next` — আসল head হলো dummy-র পরের node।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`[1,2,4]` আর `[1,3,4]` merge করতে tail জুড়ে চলে `1,1,2,3,4`, তারপর `a`-র শেষ `4` ঝুলে যায় → `[1,1,2,3,4,4]` — assert pass। একটা/দুটো খালি list-ও সঠিক (`while` চলেই না, বাকিটা ঝুলে যায়)। শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(m + n)** — প্রতিটা node ঠিক একবার করে দেখা ও জোড়া হয়; `m`, `n` দুই list-এর দৈর্ঘ্য।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(1)** — কোনো নতুন node বানাই না, শুধু arrow ঘোরাই; একটা dummy + কিছু pointer ছাড়া extra memory নেই।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- dummy head না নিয়ে শুরু করা — তখন "প্রথম node কোনটা" নিয়ে আলাদা if-else লাগে, bug বাড়ে।
- শেষে বাকি অংশ ঝোলাতে ভুলে যাওয়া (`tail.next = a if a else b`) — তখন লম্বা list-এর লেজ হারিয়ে যায়।
- `<` ব্যবহার করে stability হারানো (সমস্যা না হলেও duplicate-এ order বদলায়); `<=` নিরাপদ।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: linked list গড়া (dummy + tail, 03-এর [../../03-linked-list/](../../03-linked-list/README.md)) + merge sort-এর merge ধাপ (array ও merge-এর [পূর্বশর্ত](../../02-arrays-and-strings/README.md))। দুটো sorted run-কে এক sorted run-এ জোড়ার এই কৌশলই merge sort-এর প্রাণ।
### পরের অনুশীলন {#22-similar-harder-problems}
- Merge k Sorted Lists (দুইয়ের বদলে k-টা, heap লাগে) —