017 — Merge k Sorted Lists¶

Source¶

Original source: Classic k-way merge over sorted linked lists
Platform: LeetCode — https://leetcode.com/problems/merge-k-sorted-lists/
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

1. Problem in simple words¶

k-টা linked list দেওয়া, প্রতিটা আগে থেকে ascending sorted। তোমাকে এদের সব node মিশিয়ে একটাই sorted linked list বানাতে হবে আর তার head return করতে হবে। কিছু list খালি (None) হতে পারে; পুরো input খালিও হতে পারে (তখন উত্তর None)।

lists = [1->4->5, 1->3->4, 2->6]  ->  1->1->2->3->4->4->5->6

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-এর চেয়ে অনেক ছোট।

6. Real-life analogy¶

ভাবো k-টা আলাদা queue, প্রতিটায় ভেতরে আগে-থেকে ছোট-থেকে-বড় সাজানো লোকজন। একজন officer প্রতিবার সব queue-এর সামনের লোকদের দেখে সবচেয়ে ছোট number-ওয়ালাকে নতুন এক লাইনে পাঠান; সেই queue তখন এক ধাপ এগোয়। officer-এর চোখে একসাথে শুধু k-টা front — পুরো ভিড় না; সেই চোখটাই min-heap।

7. Visual explanation¶

lists = [1->4->5, 1->3->4, 2->6] — heap-এ প্রতি list-এর head; smallest pop করে merged-এ জোড়ো, ওই list advance করো:

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

8. Example input and output¶

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।)

9. Brute force thinking¶

প্রথম সরল চিন্তা: সব list-এর সব node-এর value একটা flat array-তে collect করো, array-টা sort করো, তারপর সেই sorted value দিয়ে নতুন একটা linked list বানাও।

সব 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)।

14. Step-by-step dry run¶

Input lists = [1->2, 0] (দুটো list: A=1->2, B=0):

heap-এ heads: (1, 0, A0), (0, 1, B0) → heapify → top (0, 1, B0)
pop (0,…,B0) → merged 0; B0.next None → push না; heap {(1,0,A0)}
pop (1,…,A0) → merged 0->1; A0.next = node(2) → push (2, 2, A1); heap {(2,2,A1)}
pop (2,…,A1) → merged 0->1->2; A1.next None → push না; heap empty
return dummy.next → 0->1->2 → flatten [0, 1, 2]

15. Python solution¶

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।

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!।

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-এর বাকি অংশ হারিয়ে যায়।

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 — https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/ (এই tracker-এর #12; same merge, matrix-এ)
Smallest Range Covering Elements from K Lists — https://leetcode.com/problems/smallest-range-covering-elements-from-k-lists/ (#20; k-way merge + window)
Merge Two Sorted Lists — https://leetcode.com/problems/merge-two-sorted-lists/ (k=2 base case)

23. Pattern learned¶

K-way merge (linked): k-টা sorted source, প্রতিটায় একটা cursor (এখানে list head); heap সবসময় বলে "এখন smallest কোথায়"। smallest নাও, merged-এ জোড়ো, সেই cursor এগোও, পরেরটা push করো। sorted source জুড়ে merge মানেই এই pattern।

24. Final summary¶

ভবিষ্যতের আমাকে: "k sorted linked list merge" = প্রতি head (value, counter, node) min-heap-এ, dummy head দিয়ে সেলাই, smallest pop → জোড়ো → পরের head push। counter tie-breaker ভুলো না, খালি list guard করো। Kth Smallest in Sorted Matrix-এর সরাসরি ভাই — একটা পারলে অন্যটাও চেনা।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।