Problem link ও উৎস
- **Original source:** Classic linked list exercise
- **Platform:** LeetCode —
- **Topic:** linked list
- **Difficulty:** Hard
- **Pattern:** merge + min-heap (priority queue)
- **Basic idea inherited from:** problem 2 (merge two) scale করা; heap-এর preview
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
`k`-টা linked list দেওয়া, প্রতিটাই আলাদাভাবে sorted (ছোট-থেকে-বড়)। তোমাকে এদের সবগুলোকে একটাই **sorted** list-এ merge করতে হবে আর তার head return করতে হবে।
```text
list1: 1 -> 4 -> 5
list2: 1 -> 3 -> 4
list3: 2 -> 6
ফল : 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6
```
### Input ও output {#8-example-input-and-output}
```text
Input : [[1,4,5], [1,3,4], [2,6]] -> Output: 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6
Edge 1 (খালি লিস্টের list): [] -> Output: None
Edge 2 (একটাই খালি list): [[]] -> Output: None
Edge 3 (কিছু খালি, কিছু না): [[], [1]] -> Output: 1
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
k-টা কাউন্টারে আলাদা আলাদা sorted লাইন। তুমি একটা মিলিত sorted লাইন বানাচ্ছ। প্রতিবার **প্রতিটা কাউন্টারের সামনের জন**-দের মধ্যে সবচেয়ে কম টোকেন-নম্বরওয়ালাকে ডাকছ। সব কাউন্টারের সামনের জনকে বারবার চোখে চোখে তুলনা না করে, একটা "সবচেয়ে ছোট আগে" যন্ত্র (heap) রাখলে কাজটা দ্রুত হয়।
## ভিত্তির ধারণা {#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)) — দুটো sorted list merge। সেখানে আমরা প্রতিবার **দুই মাথার ছোটটা** তুলতাম। এখানে দুইয়ের বদলে k-টা মাথা; তাই "সবচেয়ে ছোট মাথা" দ্রুত বের করতে দরকার একটা **heap**। এটাই heap data structure-এর প্রথম দরকারি ঝলক (preview)।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic একই invariant, scale করা: যেহেতু প্রতিটা list sorted, **সব list-এর মাথাগুলোর মধ্যে সবচেয়ে ছোটটাই** পুরো অবশিষ্ট সবকিছুর মধ্যে ক্ষুদ্রতম — সেটাই পরের output node। শুধু k-টা মাথার মধ্যে min বারবার বের করা দরকার, আর min-heap সেটা O(log k)-তে দেয়। তাই N node-এ মোট **O(N log k)**।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **min-heap** (Python-এ `heapq`) — যাতে যেকোনো মুহূর্তে k-টা list-এর মাথার মধ্যে সবচেয়ে ছোটটা O(log k)-তে তোলা যায়। সাথে merge-এর জন্য চেনা **dummy head + tail**।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
k-টা মাথা থেকে প্রতিবার min খুঁজতে সরল scan লাগত O(k); N বার করলে O(N·k)। min-heap সেই min-তোলা ও নতুন element ঢোকানো দুটোই **O(log k)**-তে করে। তাই heap ঠিক সেই operation-টা সস্তা করে যেটা ছাড়া সমাধান ধীর হতো — k বড় হলে এই পার্থক্য বিশাল।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
সরল চিন্তা: সব list-এর সব value একটা **array**-তে ঢালো, array-টা sort করো, তারপর sorted value দিয়ে একটা নতুন list বানাও।
```text
[1,4,5]+[1,3,4]+[2,6] = [1,4,5,1,3,4,2,6]
sort -> [1,1,2,3,4,4,5,6] -> নতুন list
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
প্রতিটা list **already sorted** — সেই তথ্য ফেলে দিয়ে N-টা element আবার সম্পূর্ণ sort করা মানে **O(N log N)**, যেখানে N = সব node মিলিয়ে। heap ব্যবহার করলে প্রতি pop/push O(log **k**) (k = list সংখ্যা, সাধারণত N-এর চেয়ে অনেক ছোট), তাই **O(N log k)** — কম। তাছাড়া array + নতুন node-এ O(N) extra space।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **পরের output node সবসময় k-টা list-এর বর্তমান মাথাগুলোর মধ্যে সবচেয়ে ছোটটা।** তাই পুরো খোঁজাখুঁজি নয় — শুধু একটা ছোট "min যন্ত্র"-এ k-টা মাথা রেখে বারবার ক্ষুদ্রতম তুলে নিলেই হয়, আর তোলা node-এর পরেরটা যন্ত্রে ঢুকিয়ে দিলেই হয়।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
শুরুতে প্রতিটা non-empty list-এর মাথা heap-এ ঢোকাও। তারপর বারবার: heap থেকে সবচেয়ে ছোট node তোলো, সেটা ফল-list-এর tail-এ জোড়ো, আর তার `next` (থাকলে) heap-এ push করো। heap খালি হলে শেষ। সমান value-তে tie ভাঙতে tuple-এ list index `i` রাখো, যাতে ListNode object তুলনা করতে না হয়।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "দুই list merge"-কে k-তে বাড়াতে গিয়ে nested merge না ভেবে ভাবো — "প্রতিবার শুধু সবচেয়ে ছোট মাথা চাই; এটা তো একটা min-priority-queue-র কাজ।" দুই মাথার তুলনা → k মাথার min, আর min-এর জন্য heap — এই এক লাফেই brute force থেকে optimal-এ।
### ছবিতে বোঝা {#7-visual-explanation}
Input lists: `[1,4,5]`, `[1,3,4]`, `[2,6]`। Heap-এর প্রতিটি pair `(value,list ID)`; table-এ heap-এর members পড়ার সুবিধায় sorted, internal heap array নয়।
| ধাপ | pop | নতুন push | output | heap members |
| --- | --- | --- | --- | --- |
| 1 | (1,L1) | (4,L1) | `[1]` | `(1,L2), (2,L3), (4,L1)` |
| 2 | (1,L2) | (3,L2) | `[1, 1]` | `(2,L3), (3,L2), (4,L1)` |
| 3 | (2,L3) | (6,L3) | `[1, 1, 2]` | `(3,L2), (4,L1), (6,L3)` |
| 4 | (3,L2) | (4,L2) | `[1, 1, 2, 3]` | `(4,L1), (4,L2), (6,L3)` |
| 5 | (4,L1) | (5,L1) | `[1, 1, 2, 3, 4]` | `(4,L2), (5,L1), (6,L3)` |
| 6 | (4,L2) | — | `[1, 1, 2, 3, 4, 4]` | `(5,L1), (6,L3)` |
| 7 | (5,L1) | — | `[1, 1, 2, 3, 4, 4, 5]` | `(6,L3)` |
| 8 | (6,L3) | — | `[1, 1, 2, 3, 4, 4, 5, 6]` | `empty` |
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `[[1,4],[2]]`:
1. push মাথা: `heap = {(1,0,n1), (2,1,n2)}` (n1 = list0-এর 1, n2 = list1-এর 2)।
2. pop `(1,0,n1)` → out `1`; n1.next = 4 push → `heap = {(2,1,n2),(4,0,n4)}`।
3. pop `(2,1,n2)` → out `1 2`; n2.next = None, push নয় → `heap = {(4,0,n4)}`।
4. pop `(4,0,n4)` → out `1 2 4`; n4.next = None → `heap = {}`।
5. heap খালি → শেষ। ফল `1 -> 2 -> 4`।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
import heapq
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def merge_k_lists(lists):
heap = []
# প্রতিটা non-empty list-এর মাথা push; i = tie ভাঙার জন্য list index
for i, node in enumerate(lists):
if node:
heapq.heappush(heap, (node.val, i, node))
dummy = ListNode() # dummy head — head-এর special case এড়াতে
tail = dummy
while heap:
val, i, node = heapq.heappop(heap) # সবচেয়ে ছোট মাথা
tail.next = node
tail = tail.next
if node.next: # তোলা node-এর পরেরটা heap-এ
heapq.heappush(heap, (node.next.val, i, node.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(merge_k_lists([build([1, 4, 5]), build([1, 3, 4]), build([2, 6])])) == [1, 1, 2, 3, 4, 4, 5, 6]
assert to_list(merge_k_lists([])) == []
assert to_list(merge_k_lists([build([])])) == []
assert to_list(merge_k_lists([build([]), build([1])])) == [1]
assert to_list(merge_k_lists([build([2, 2]), build([2])])) == [2, 2, 2] # tie ভাঙা
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `import heapq` — Python-এর min-heap (priority queue)।
- প্রথম loop — প্রতিটা list-এর মাথা `(val, i, node)` রূপে push; খালি list বাদ।
- `(node.val, i, node)` — heap val দিয়ে sort করে; সমান val-এ `i` (list index) tie ভাঙে, যাতে ListNode তুলনা করতে না হয় (object তুলনায় error)।
- `heapq.heappop(heap)` — বর্তমান k মাথার মধ্যে সবচেয়ে ছোটটা O(log k)-তে।
- `tail.next = node; tail = tail.next` — তোলা node ফল-list-এ জোড়ো।
- `if node.next: heappush(...)` — তোলা node-এর পরের node heap-এ ঢোকাও, যাতে সেই list এগোয়।
- `return dummy.next` — আসল head।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`[[1,4,5],[1,3,4],[2,6]]`: শুরুতে heap-এ তিন মাথা (1,1,2)। বারবার ছোটটা তুলে আর পরেরটা push করে output দাঁড়ায় `1 1 2 3 4 4 5 6` → `[1,1,2,3,4,4,5,6]` — assert pass। খালি, এক-খালি, মিশ্র, সমান-value (tie) — সব pass; শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(N log k)** — N = সব list মিলিয়ে মোট node; প্রতিটা node একবার push + একবার pop, প্রতিটা heap operation O(log k) (heap-এ সর্বোচ্চ k element)।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(k)** — heap-এ একসাথে সর্বোচ্চ k-টা node (প্রতি list থেকে একটা মাথা)। ফল-list পুরোনো node reuse করে, তাই বাড়তি নয়।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- heap tuple-এ tie-breaker না দেওয়া (`(val, node)`) — সমান val-এ Python ListNode তুলনা করতে গিয়ে `TypeError`। তাই মাঝে `i` (বা একটা counter) রাখো।
- শুরুতে খালি list push করা — `node` None হলে crash; তাই `if node:` চেক করো।
- তোলা node-এর `next` push করতে ভুলে যাওয়া — তখন সেই list আর এগোয় না, output অসম্পূর্ণ।
- `lists` খালি (`[]`) আলাদা না ভাবা — heap খালি থাকে, `dummy.next` = None ঠিকঠাক ফেরে (এই code-এ এমনিতেই সামলায়)।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: merge two sorted lists ([[002-merge-two-sorted-lists.md](002-merge-two-sorted-lists.md)](002-merge-two-sorted-lists.md)) — দুই মাথার ছোটটা তোলার idea k-তে বাড়ানো, min খুঁজতে heap যোগ করে। dummy head কৌশলও সেখান থেকেই।
### পরের অনুশীলন {#22-similar-harder-problems}
- Merge Two Sorted Lists (এই problem-এর বীজ) —