Problem link ও উৎস
- **Original source:** Classic linked-list / recursion exercise
- **Platform:** LeetCode —
- **Topic:** recursion (decrease-and-conquer on lists)
- **Difficulty:** Easy
- **Pattern:** decrease-and-conquer — ছোট head বেছে বাকিটা recursively merge
- **Basic idea inherited from:** linked lists section + leap of faith
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
দুটো sorted (ছোট থেকে বড় সাজানো) singly linked list দেওয়া আছে। তোমার কাজ: ওদের জোড়া লাগিয়ে একটা নতুন sorted list বানানো, যাতে দুই list-এর সব node ঠিক একবার করে থাকে আর সব মিলিয়ে sorted থাকে। নতুন list-এর head return করো।
```text
list1 : 1 -> 2 -> 4
list2 : 1 -> 3 -> 4
merge : 1 -> 1 -> 2 -> 3 -> 4 -> 4
```
### Input ও output {#8-example-input-and-output}
```text
Input : 1->2->4 , 1->3->4 -> Output: 1->1->2->3->4->4
Input : 5 , 1->2->3 -> Output: 1->2->3->5
Edge case 1 (দুটোই খালি): None , None -> Output: None
Edge case 2 (একটা খালি): None , 0->1 -> Output: 0->1
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
দুই গোছা তাস ভাবো, প্রতি গোছা নিজে নিজে ছোট-থেকে-বড় সাজানো, মুখ নিচু করে রাখা। তুমি প্রতিবার দুই গোছার উপরের তাস দুটো দেখে যেটা ছোট সেটা তুলে নতুন stack-এ রাখো। এক গোছা শেষ হলে, বাকি গোছাটা যেমন আছে তেমন বসিয়ে দাও — কারণ সেটা তো এমনিতেই sorted।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
ভিত্তি হলো **linked lists section + leap of faith**। দুটো sorted list-এর মধ্যে যেটার head ছোট, সেটাই পুরো merged list-এর head হবে — এটা নিশ্চিত। তারপর সেই head-এর `next`-এ বসবে "বাকি অংশ আর অন্য list-এর merge"। ওই বাকি merge-টা recursion-কে বিশ্বাস করে দিয়ে দাও (leap of faith); নিজে ভেতরে ঢুকে trace কোরো না।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic একটা **invariant**: যেকোনো মুহূর্তে দুই list-এর দুই head-ই নিজ নিজ list-এর সবচেয়ে ছোট অবশিষ্ট element। তাই ওই দুইয়ের মধ্যে ছোটটাই গোটা অবশিষ্ট merge-এর সবচেয়ে ছোট element — সেটাকে সামনে বসিয়ে বাকি problem এক node ছোট করে দাও। প্রতি step-এ ঠিক একটা node স্থায়ীভাবে জায়গা পায়।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
**Linked list নিজেই** — নতুন কোনো structure লাগে না। আমরা শুধু বিদ্যমান node-গুলোর `next` pointer আবার বাঁধি (rewire), নতুন node বানাই না। recursion-এর জন্য **call stack** লাগে।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
Linked list-এ একটা node-কে অন্যটার সামনে জোড়া দেওয়া মানে শুধু একটা `next` pointer বদলানো — O(1)। array হলে মাঝখানে ঢোকাতে shift করতে হতো (O(n))। যেহেতু merge মানে বারবার "ছোট head-টা সামনে আনো", linked list-এর সস্তা pointer-rewiring এটাকে নিখুঁতভাবে মানায়, কোনো বাড়তি memory ছাড়াই।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: দুই list-এর সব value একটা array-তে ঢালো, array-টা sort করো, তারপর সেই array থেকে নতুন একটা linked list বানাও।
```text
1) দুই list ঘুরে -> [1,2,4,1,3,4]
2) sort -> [1,1,2,3,4,4]
3) নতুন list বানাও
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
কাজ করে, কিন্তু দুটো অপচয়: (a) array sort করতে **O(m+n log(m+n))**, অথচ input তো আগেই sorted — এই তথ্য নষ্ট হলো; (b) **O(m+n) extra space** (array + নতুন node)। অথচ দুই head তুলনা করেই linear সময়ে, পুরোনো node গুলো rewire করে, কম জায়গায় merge করা যায়।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **দুই sorted head-এর মধ্যে ছোটটাই merged list-এর পরের element** — এর চেয়ে ছোট আর কিছু কোনো list-এ নেই। তাই পুরো list একসাথে না ভেবে, শুধু "এই মুহূর্তে কোন head ছোট" ঠিক করো, সেটা বসাও, বাকিটা recursion-কে দাও।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
Base case: কোনো list `None` হলে অন্যটা যেমন আছে তেমন ফেরত দাও (sorted তো বটেই)। নাহলে দুই head তুলনা করো; ছোট head-টা রাখো, তার `next`-এ বসাও "ওই head বাদ দিয়ে বাকি অংশ আর অন্য list-এর merge"। সেই ছোট head-ই এই level-এর উত্তর। leap of faith: ভেতরের merge ঠিক করবে — তুমি শুধু এই এক জোড়া তুলনা সামলাও।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "দুটো পুরো list কীভাবে মেশাব?" ভাবার বদলে জিজ্ঞেস করো "merged list-এর সবচেয়ে প্রথম node-টা কে?" — অবশ্যই দুই head-এর ছোটটা। ওটা বসিয়ে দিলে বাকি কাজটা ঠিক একই ধরনের, এক node ছোট problem; recursion-কে বিশ্বাস করো।
### ছবিতে বোঝা {#7-visual-explanation}
প্রতি call ছোট head বেছে বাকিটার merge-কে তার `next`-এ বসায় — single chain, গভীরতা = মোট node সংখ্যা:
```text
merge(1a->2->4 , 1b->3->4)
1a <= 1b -> 1a.next = merge(2->4 , 1b->3->4)
1b < 2 -> 1b.next = merge(2->4 , 3->4)
2 < 3 -> 2.next = merge(4 , 3->4)
3 < 4 -> 3.next = merge(4 , 4)
4 <= 4 -> 4a.next = merge(None , 4)
list1 None -> return list2 (4) [base case]
ফলাফল গাঁথা: 1a -> 1b -> 2 -> 3 -> 4a -> 4
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
`merge(1->3, 2->4)`:
1. `1 <= 2` → head = node `1`; `1.next = merge(3, 2->4)`।
2. `3 > 2` → head = node `2`; `2.next = merge(3, 4)`।
3. `3 <= 4` → head = node `3`; `3.next = merge(None, 4)`।
4. list1 `None` → base case, return `4`।
5. unwind করে গাঁথা হয়: `1 -> 2 -> 3 -> 4`।
## কোড ও ব্যাখ্যা {#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(l1, l2):
if l1 is None: # base case: এক list শেষ
return l2
if l2 is None:
return l1
if l1.val <= l2.val: # ছোট head বেছে নাও
l1.next = merge_two_lists(l1.next, l2)
return l1
else:
l2.next = merge_two_lists(l1, l2.next)
return l2
# ---- 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([5]), build([1, 2, 3]))) == [1, 2, 3, 5]
assert to_list(merge_two_lists(build([]), build([]))) == [] # দুটোই খালি
assert to_list(merge_two_lists(build([]), build([0, 1]))) == [0, 1] # একটা খালি
assert to_list(merge_two_lists(build([1, 1]), build([1, 1]))) == [1, 1, 1, 1] # সব সমান
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `if l1 is None: return l2` / `if l2 is None: return l1` — base case: এক list ফুরালে বাকিটা পুরোটা জুড়ে দাও।
- `if l1.val <= l2.val:` — দুই head তুলনা; `<=` রাখায় সমান হলে stable থাকে।
- `l1.next = merge_two_lists(l1.next, l2)` — `l1`-এর head রেখে তার পরের অংশ ও `l2`-কে merge করে পেছনে জোড়া।
- `return l1` / `return l2` — যে head ছোট, সেটাই এই level-এর merged head।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`merge_two_lists(build([1,2,4]), build([1,3,4]))`: প্রতি ধাপে ছোট head বসে — 1,1,2,3,4,4 গাঁথা হয়, `to_list` দেয় `[1,1,2,3,4,4]`। `[5]` ও `[1,2,3]`-এ 5 শেষে বসে। দুটো খালি → `None` → `[]`। এক খালি → অন্যটা সরাসরি। সব-সমান case-ও ঠিক, তারপর print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(m + n)** — প্রতিটা node ঠিক একবার তুলনা ও rewire হয়; m, n দুই list-এর দৈর্ঘ্য।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(m + n)** recursion stack-এর জন্য (প্রতি node-এ এক level গভীর)। Iterative version-এ **O(1)** — নতুন node বানে না, শুধু pointer rewire।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- base case (এক list `None`) না রাখা — `None.val`-এ crash।
- `<` ব্যবহার করে সমান value-তে stability নষ্ট করা; `<=` নিরাপদ।
- recursion-এর ফল `next`-এ assign করতে ভুলে যাওয়া — তখন বাকি অংশ হারিয়ে যায়।
- নতুন node বানিয়ে memory নষ্ট করা — পুরোনো node rewire করলেই হয়।
- Python-এ খুব লম্বা list-এ depth limit — তখন iterative দুই-pointer version বেছে নাও।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: linked-list traversal ([../../03-linked-list/](../../03-linked-list/README.md)) + leap of faith ([../concept.md](../concept.md))। এটাই Merge Sort-এর combine step; [../patterns.md](../patterns.md)-এর Pattern 1 (decrease-and-conquer) দেখো। আটকে গেলে আগে Reverse Linked List ([../../03-linked-list/problems/001-reverse-linked-list.md](../../03-linked-list/problems/001-reverse-linked-list.md)) ঝালিয়ে নাও।
### পরের অনুশীলন {#22-similar-harder-problems}
- Merge k Sorted Lists —