Problem link ও উৎস
- **Original source:** Classic linked list exercise
- **Platform:** LeetCode —
- **Topic:** linked list
- **Difficulty:** Easy
- **Pattern:** merge + dummy head
- **Basic idea inherited from:** দুটো sorted জিনিস merge করা (two-pointer merge, [../../02-arrays-and-strings/](../../02-arrays-and-strings/README.md))
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
দুটো linked list দেওয়া আছে, দুটোই ছোট-থেকে-বড় (sorted)। তোমার কাজ: এদের একটা নতুন **sorted** list-এ গেঁথে দাও (zip করো), যেখানে দুটোর সব node থাকবে, ক্রম ঠিক রেখে। নতুন list-এর head return করো।
```text
list1: 1 -> 3 -> 5
list2: 2 -> 4 -> 6
ফল : 1 -> 2 -> 3 -> 4 -> 5 -> 6
```
### Input ও output {#8-example-input-and-output}
```text
Input : l1 = 1 -> 3 -> 5 , l2 = 2 -> 4 -> 6
Output: 1 -> 2 -> 3 -> 4 -> 5 -> 6
Edge 1: l1 = None , l2 = 1 -> 2 -> Output: 1 -> 2
Edge 2: l1 = None , l2 = None -> Output: None
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
দুই হাতে দুই গোছা তাস, দুটোই sorted। তুমি নতুন একটা গোছা বানাচ্ছ — প্রতিবার দুই গোছার **উপরের** তাস দুটো দেখে ছোটটা নতুন গোছায় রাখছ। এক গোছা শেষ হলে বাকিটা পুরো ঢেলে দিচ্ছ।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এটা merge sort-এর সেই বিখ্যাত **merge step**-এরই linked list রূপ — দুটো sorted জিনিস থেকে প্রতিবার ছোট মাথাটা তুলে নেওয়া। array-তে যেটা two-pointer merge ([../../02-arrays-and-strings/](../../02-arrays-and-strings/README.md)), এখানে সেটাই pointer দিয়ে।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
Invariant: যেহেতু দুই list sorted, যেকোনো মুহূর্তে দুই list-এর **মাথার ছোটটাই** পুরো বাকি সবকিছুর মধ্যে সবচেয়ে ছোট। তাই বারবার দুই মাথা তুলনা করে ছোটটা নিলেই ফল আপনাআপনি sorted থাকে।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
কোনো নতুন structure নয় — শুধু একটা **dummy head** node আর একটা `tail` pointer। dummy head হলো একটা নকল শুরুর node, যাতে "প্রথম node-টা কে" সেই বিশেষ ক্ষেত্রটা আলাদা করে ভাবতে না হয়।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
Linked list-এ node যোগ করা মানে শুধু একটা arrow সেট করা — O(1)। dummy head থাকায় আমরা প্রতিটা node-কে একইভাবে `tail.next`-এ জুড়তে পারি, এমনকি একদম প্রথমটাকেও। এতে edge case (খালি ফল-list) আলাদা করে সামলাতে হয় না — code পরিষ্কার থাকে।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
সরল চিন্তা: দুই list-এর সব value একটা array-তে ঢালো, array sort করো, তারপর নতুন list বানাও।
```text
[1,3,5] + [2,4,6] = [1,3,5,2,4,6] -> sort -> [1,2,3,4,5,6] -> নতুন list
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
দুটো জিনিস **already sorted** — সেই সুবিধা ফেলে দিয়ে আবার sort করা অপচয় (O(n log n))। তাছাড়া array + নতুন node = O(n) extra space। sorted অবস্থা কাজে লাগালে O(n) সময়ে, পুরোনো node গুলো reuse করেই হয়ে যায়।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
যেহেতু দুটোই sorted, **প্রতি মুহূর্তে পরের সঠিক node হলো দুই মাথার ছোটটা** — পুরো খোঁজাখুঁজির দরকার নেই, শুধু দুই মাথা তুলনা।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
একটা dummy head বানাও, একটা `tail` রাখো। যতক্ষণ দুই list-এই node আছে, ছোট-মাথাওয়ালাটা `tail`-এ জুড়ে সেই list এক ঘর এগিয়ে দাও। একটা শেষ হলে অন্যটার বাকি অংশ সরাসরি `tail`-এ লাগিয়ে দাও (ওটা তো এমনিতেই sorted)।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "প্রথম node কোনটা হবে" নিয়ে মাথা না ঘামিয়ে একটা **dummy head** বসিয়ে দাও — তাহলে সব node একইভাবে জোড়া যায়, শেষে `dummy.next` ফেরত দিলেই আসল head।
### ছবিতে বোঝা {#7-visual-explanation}
dummy থেকে শুরু, `tail` সবসময় ফল-list-এর শেষে:
```text
l1: 1 -> 3 -> 5 l2: 2 -> 4 -> 6
dummy -> ?
1 <= 2 → 1 নাও: dummy -> 1 (l1 = 3->5)
3 > 2 → 2 নাও: dummy -> 1 -> 2 (l2 = 4->6)
3 <= 4 → 3 নাও: dummy -> 1 -> 2 -> 3 (l1 = 5)
5 > 4 → 4 নাও: dummy -> 1 -> 2 -> 3 -> 4 (l2 = 6)
5 <= 6 → 5 নাও: dummy -> 1 -> 2 -> 3 -> 4 -> 5 (l1 = None)
l1 শেষ → বাকি l2 (6) পুরো জুড়ে দাও: dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> 6
return dummy.next = 1 -> 2 -> 3 -> 4 -> 5 -> 6
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
`l1 = 1->3`, `l2 = 2->4`:
1. `dummy`, `tail=dummy`
2. `1 <= 2` → `tail.next=1`, `l1=3`, `tail=1`
3. `3 > 2` → `tail.next=2`, `l2=4`, `tail=2`
4. `3 <= 4` → `tail.next=3`, `l1=None`, `tail=3`
5. `l1=None` → loop শেষ; `tail.next = l2 (4)`
6. return `dummy.next` = `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):
dummy = ListNode() # নকল শুরু — head-এর special case এড়াতে
tail = dummy
while l1 and l2:
if l1.val <= l2.val:
tail.next = l1 # ছোট মাথাটা জুড়ো
l1 = l1.next
else:
tail.next = l2
l2 = l2.next
tail = tail.next # tail সবসময় শেষে
tail.next = l1 if l1 else l2 # যেটা বাকি, পুরো জুড়ে দাও
return dummy.next
# ---- helpers ----
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, 3, 5]), build([2, 4, 6]))) == [1, 2, 3, 4, 5, 6]
assert to_list(merge_two_lists(build([]), build([1, 2]))) == [1, 2]
assert to_list(merge_two_lists(build([]), build([]))) == []
assert to_list(merge_two_lists(build([1, 1]), build([1]))) == [1, 1, 1] # সমান value
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `dummy = ListNode()` — নকল head, যাতে প্রথম node-ও সাধারণভাবে জোড়া যায়।
- `tail = dummy` — `tail` সবসময় ফল-list-এর শেষ node।
- `while l1 and l2:` — যতক্ষণ **দুটোতেই** node আছে।
- `if l1.val <= l2.val:` — ছোট (বা সমান) মাথাটা বাছো; `<=` রাখায় stable থাকে।
- `tail.next = ...; ... = ....next` — বাছা node জুড়ে, সেই list এগোও।
- `tail = tail.next` — `tail` শেষে সরাও।
- `tail.next = l1 if l1 else l2` — একটা শেষ; বাকিটা already sorted, পুরো জুড়ে দাও।
- `return dummy.next` — আসল head।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`[1,3,5]` ও `[2,4,6]` merge হয়ে `[1,2,3,4,5,6]`। খালি+`[1,2]` → `[1,2]`; খালি+খালি → `[]`; `[1,1]`+`[1]` → `[1,1,1]` (সমান value ঠিকভাবে সামলায়)। সব assert pass → `সব test pass!`।
### JavaScript ও test cases {#25-javascript-solution-with-test-cases}
```javascript
const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };
class ListNode {
constructor(val = 0, next = null) { this.val = val; this.next = next; }
}
const arrayToList = (arr) => {
const dummy = new ListNode();
let tail = dummy;
for (const v of arr) { tail.next = new ListNode(v); tail = tail.next; }
return dummy.next;
};
const listToArray = (head) => {
const out = [];
while (head) { out.push(head.val); head = head.next; }
return out;
};
function mergeTwoLists(l1, l2) {
const dummy = new ListNode(); // নকল শুরু — head-এর special case এড়াতে
let tail = dummy;
while (l1 && l2) {
if (l1.val <= l2.val) { tail.next = l1; l1 = l1.next; } // ছোট মাথাটা জুড়ো
else { tail.next = l2; l2 = l2.next; }
tail = tail.next; // tail সবসময় শেষে
}
tail.next = l1 || l2; // যেটা বাকি, পুরো জুড়ে দাও
return dummy.next;
}
// ---- test cases ----
const eq = (a, b) => JSON.stringify(a) === JSON.stringify(b);
assert(eq(listToArray(mergeTwoLists(arrayToList([1, 3, 5]), arrayToList([2, 4, 6]))), [1, 2, 3, 4, 5, 6]), "main");
assert(eq(listToArray(mergeTwoLists(arrayToList([]), arrayToList([1, 2]))), [1, 2]), "one empty");
assert(eq(listToArray(mergeTwoLists(arrayToList([]), arrayToList([]))), []), "both empty");
assert(eq(listToArray(mergeTwoLists(arrayToList([1, 1]), arrayToList([1]))), [1, 1, 1]), "সমান value");
console.log("সব JS test pass!");
```
> **JS টীকা:** `tail.next = l1 || l2` হলো idiomatic JS — `l1` যদি `null` হয় তবে `l2` বসে, কারণ `null` falsy। dummy head ব্যবহার করায় প্রথম node-ও সাধারণভাবে `tail.next`-এ জুড়ে যায়, খালি-ফল edge case আলাদা সামলাতে হয় না। `<=` রাখলে সমান value-তে stable order থাকে। পুরোনো node গুলোই reuse হয়, নতুন node বানানো হয় না — O(1) extra space।
### TypeScript ও test cases {#26-typescript-solution-with-test-cases}
```typescript
interface ListNode { val: number; next: ListNode | null }
const node = (val: number, next: ListNode | null = null): ListNode => ({ val, next });
const arrayToList = (arr: number[]): ListNode | null => {
let head: ListNode | null = null;
for (let i = arr.length - 1; i >= 0; i--) head = node(arr[i], head);
return head;
};
const listToArray = (head: ListNode | null): number[] => {
const out: number[] = [];
while (head) { out.push(head.val); head = head.next; }
return out;
};
function mergeTwoLists(l1: ListNode | null, l2: ListNode | null): ListNode | null {
const dummy: ListNode = node(0);
let tail: ListNode = dummy;
while (l1 && l2) {
if (l1.val <= l2.val) { tail.next = l1; l1 = l1.next; }
else { tail.next = l2; l2 = l2.next; }
tail = tail.next;
}
tail.next = l1 ?? l2; // যেটা non-null
return dummy.next;
}
function expect