Problem link ও উৎস
- **Original source:** Classic k-way merge over sorted linked lists
- **Platform:** LeetCode —
- **Topic:** heap / priority queue
- **Difficulty:** Hard
- **Pattern:** K-way merge (প্রতি list-এর head একটা heap-এ)
- **Basic idea inherited from:** `03-linked-list` pointer-stitching + `08` k-way merge
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
`k`-টা linked list দেওয়া, প্রতিটা **আগে থেকে ascending sorted**। তোমাকে এদের সব node মিশিয়ে **একটাই sorted linked list** বানাতে হবে আর তার head return করতে হবে। কিছু list খালি (`None`) হতে পারে; পুরো input খালিও হতে পারে (তখন উত্তর `None`)।
```text
lists = [1->4->5, 1->3->4, 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]
Input : [] -> Output: [] (কোনো list নেই)
Input : [[]] -> Output: [] (একটাই খালি list)
Input : [[1],[0]] -> Output: [0,1]
```
(উপরে list-গুলো array আকারে দেখানো; আসল input/output linked list।)
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো k-টা আলাদা queue, প্রতিটায় ভেতরে আগে-থেকে ছোট-থেকে-বড় সাজানো লোকজন। একজন officer প্রতিবার সব queue-এর **সামনের লোকদের** দেখে সবচেয়ে ছোট number-ওয়ালাকে নতুন এক লাইনে পাঠান; সেই queue তখন এক ধাপ এগোয়। officer-এর চোখে একসাথে শুধু k-টা front — পুরো ভিড় না; সেই চোখটাই min-heap।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
ভিত দুটো। `03-linked-list`-এর **pointer stitching** — dummy head নিয়ে `tail.next` জোড়া দিয়ে নতুন list বানানো। আর `08`-এর **k-way merge** — overall-এর পরের node সবসময় সব list-এর current head-দের মধ্যে smallest, যেটা একটা heap O(log k)-এ দেয়।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic: প্রতিটা list sorted বলে একটা list থেকে শুধু তার **current head**-ই পরবর্তী candidate। k-টা head-এর মধ্যে সবচেয়ে ছোটটাই merged list-এর পরের node। সেটা নেওয়ার পরে ওই list-এর head এক ধাপ এগোয়, আর নতুন head (থাকলে) candidate-pool-এ ঢোকে। এটা two-pointer merge-এরই k-pointer সাধারণীকরণ।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **min-heap** যেখানে প্রতি non-empty list-এর current head node থাকে। node সরাসরি compare করা যায় না (LeetCode-এ), তাই heap-এ `(value, tie_breaker, node)` রাখি; `tie_breaker` একটা বাড়তে-থাকা counter, যাতে value সমান হলে heap কখনো node compare না করে।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
heap-এ কখনো k-টার বেশি entry থাকে না — প্রতি list-এর একটা head। smallest peek O(1)-সম, pop/push O(log k)। N মোট node-এর জন্য মোট O(N log k) — "সব node এক জায়গায় ঢেলে sort" (O(N log N)) থেকে ভালো, কারণ k সাধারণত N-এর চেয়ে অনেক ছোট।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: সব list-এর সব node-এর value একটা flat array-তে collect করো, array-টা sort করো, তারপর সেই sorted value দিয়ে নতুন একটা linked list বানাও।
```text
সব value নাও -> [1,4,5,1,3,4,2,6] -> sort -> [1,1,2,3,4,4,5,6] -> list বানাও
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
সব N node collect করে sort করা মানে **O(N log N)** time আর O(N) extra space, আর list-গুলোর already-sorted গঠন কাজেই লাগানো হলো না। k-way merge সেই গঠন কাজে লাগিয়ে O(N log k)-তে নামে; k ছোট হলে (যা প্রায়ই হয়) এটা স্পষ্টভাবে দ্রুত। (একে একে দুই list merge করা গেলে O(N·k) হয়, আরও খারাপ।)
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: পরের merged node সবসময় **k-টা current head-এর মধ্যে smallest**। তাই পুরো কিছু sort না করে, শুধু k-টা head একটা heap-এ রাখো; smallest pop করো, merged-এ জোড়ো, সেই list-এর পরের head push করো। heap কখনো k-এর বেশি বড় হয় না।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
প্রতিটা non-empty list-এর head `(value, counter, node)` হিসেবে heap-এ ঢালো (counter tie-break করে)। একটা dummy head আর tail pointer নাও। Loop যতক্ষণ heap non-empty: smallest pop করো, সেই node-কে `tail.next`-এ জোড়ো, tail এগোও; ওই node-এর `next` থাকলে সেটা heap-এ push করো। শেষে `dummy.next` return করো।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "k-টা list একসাথে merge" না ভেবে ভাবো "k-টা cursor, প্রতিবার heap বলে দেয় কোন cursor-এ এখন smallest; সেটা নাও, সেই cursor এগোও।" "merge k sorted ... / k sorted streams" — এই কথা শুনলেই k-way merge heap-এর কথা মাথায় আসা উচিত, ঠিক Kth Smallest in Sorted Matrix-এর মতো (#12)।
### ছবিতে বোঝা {#7-visual-explanation}
`lists = [1->4->5, 1->3->4, 2->6]` — heap-এ প্রতি list-এর head; smallest pop করে merged-এ জোড়ো, ওই list advance করো:
```text
heap heads: 1(A) 1(B) 2(C)
pop 1(A) -> merged 1 ; push 4(A) heap: 1(B) 2(C) 4(A)
pop 1(B) -> merged 1 ; push 3(B) heap: 2(C) 3(B) 4(A)
pop 2(C) -> merged 2 ; push 6(C) heap: 3(B) 4(A) 6(C)
pop 3(B) -> merged 3 ; push 4(B) heap: 4(A) 4(B) 6(C)
pop 4(A) -> merged 4 ; push 5(A) heap: 4(B) 5(A) 6(C)
pop 4(B) -> merged 4 ; B শেষ heap: 5(A) 6(C)
pop 5(A) -> merged 5 ; A শেষ heap: 6(C)
pop 6(C) -> merged 6 ; C শেষ heap empty
merged: 1->1->2->3->4->4->5->6
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `lists = [1->2, 0]` (দুটো list: A=1->2, B=0):
1. heap-এ heads: (1, 0, A0), (0, 1, B0) → heapify → top (0, 1, B0)
2. pop (0,…,B0) → merged `0`; B0.next None → push না; heap {(1,0,A0)}
3. pop (1,…,A0) → merged `0->1`; A0.next = node(2) → push (2, 2, A1); heap {(2,2,A1)}
4. pop (2,…,A1) → merged `0->1->2`; A1.next None → push না; heap empty
5. return dummy.next → `0->1->2` → flatten [0, 1, 2]
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
import heapq
class ListNode:
def __init__(self, val=0, nxt=None):
self.val = val
self.next = nxt
def merge_k_lists(lists):
heap = []
counter = 0 # tie-breaker: value সমান হলে node compare এড়াতে
for node in lists:
if node: # খালি list বাদ
heapq.heappush(heap, (node.val, counter, node))
counter += 1
dummy = ListNode()
tail = dummy
while heap:
val, _, node = heapq.heappop(heap) # k head-এর মধ্যে smallest
tail.next = node # merged list-এ জোড়ো
tail = node
if node.next: # ওই list-এ পরের node?
heapq.heappush(heap, (node.next.val, counter, node.next))
counter += 1
return dummy.next
# ---- helpers (test-এর জন্য) ----
def build(arr):
dummy = ListNode()
t = dummy
for x in arr:
t.next = ListNode(x)
t = t.next
return dummy.next
def flatten(node):
out = []
while node:
out.append(node.val)
node = node.next
return out
# ---- tests ----
r1 = merge_k_lists([build([1, 4, 5]), build([1, 3, 4]), build([2, 6])])
assert flatten(r1) == [1, 1, 2, 3, 4, 4, 5, 6]
assert merge_k_lists([]) is None # কোনো list নেই
assert merge_k_lists([build([])]) is None # একটাই খালি list
r2 = merge_k_lists([build([1]), build([0])])
assert flatten(r2) == [0, 1]
r3 = merge_k_lists([build([-2, -1, -1]), build([-3, 0]), build([])])
assert flatten(r3) == [-3, -2, -1, -1, 0]
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `class ListNode` — সাধারণ singly linked-list node (`03-linked-list`-এর মতো)।
- `counter` — tie-breaker; value সমান হলে heap যাতে `ListNode` object compare করতে গিয়ে error না দেয়।
- `if node: heappush(heap, (node.val, counter, node))` — শুধু non-empty list-এর head heap-এ; tuple-এ value প্রথমে বলে value দিয়েই order হয়।
- `dummy = ListNode(); tail = dummy` — নতুন merged list সেলাই করার আদর্শ dummy-head trick।
- `val, _, node = heappop(heap)` — k head-এর মধ্যে smallest node।
- `tail.next = node; tail = node` — সেই node-কে merged list-এর শেষে জুড়ে tail এগোও।
- `if node.next: heappush(...)` — ওই list-এর পরের head heap-এ ঢালো, counter বাড়াও।
- `return dummy.next` — dummy-র পরেরটাই আসল merged head।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`merge_k_lists([1->2, 0])` section 14-এর dry run মেনে 0->1->2 দেয় (flatten [0,1,2])। main example flatten করলে [1,1,2,3,4,4,5,6]; খালি input আর `[[]]` দুটোই `None`; negative + খালি-list-মিশ্রিত input-ও সঠিক sorted দেয়। merged order নির্দিষ্ট (sorted), তাই flatten করে সরাসরি সমতা assert। সব pass-এর পরে print হয়: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(N log k)** — N = মোট node সংখ্যা, k = list সংখ্যা। প্রতিটা node ঠিক একবার heap-এ ঢোকে আর একবার বেরোয়, আর heap-এ কখনো k-এর বেশি entry থাকে না, তাই প্রতিটা op O(log k)।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(k)** — heap-এ বড়জোর k-টা head entry। output list নতুন node বানায় না (existing node গুলোই re-link করা হয়), তাই extra space heap-টুকুই।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- heap-এ tie-breaker না রাখা — value সমান হলে Python `ListNode` compare করতে গিয়ে `TypeError` দেবে।
- খালি list (`None`) head heap-এ ঢালা — শুরুতেই `if node:` দিয়ে guard না দিলে crash।
- dummy head ব্যবহার না করে head edge-case হাতে সামলানো — সহজেই off-by-one/None bug।
- pop করা node-এর `next` push করতে ভুলে যাওয়া — তখন ওই list-এর বাকি অংশ হারিয়ে যায়।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি `03-linked-list`-এর pointer stitching (dummy head, tail-এ জোড়া) আর `08`-এর `patterns.md`-র Pattern 2 (K-way merge)। এটা two-pointer merge-এর k-pointer রূপ — কোন pointer নড়বে সেটা heap ঠিক করে। Kth Smallest in Sorted Matrix (#12)-এর সাথে যমজ।
### পরের অনুশীলন {#22-similar-harder-problems}
- Kth Smallest Element in a Sorted Matrix —