017 — Merge k Sorted Lists

অধ্যায় · সমস্ত অনুশীলন ও উৎস · ধাপে ধাপে শেখা

Problem link ও উৎস

• 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

প্রশ্ন ও উদাহরণ

সহজ করে প্রশ্ন

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

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

চেনা উদাহরণে বোঝা

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

ভিত্তির ধারণা

আগের কোন ধারণাটি লাগবে

ভিত দুটো। 03-linked-list-এর pointer stitching — dummy head নিয়ে tail.next জোড়া দিয়ে নতুন list বানানো। আর 08-এর k-way merge — overall-এর পরের node সবসময় সব list-এর current head-দের মধ্যে smallest, যেটা একটা heap O(log k)-এ দেয়।

ভেতরের যুক্তি

লুকানো logic: প্রতিটা list sorted বলে একটা list থেকে শুধু তার current head-ই পরবর্তী candidate। k-টা head-এর মধ্যে সবচেয়ে ছোটটাই merged list-এর পরের node। সেটা নেওয়ার পরে ওই list-এর head এক ধাপ এগোয়, আর নতুন head (থাকলে) candidate-pool-এ ঢোকে। এটা two-pointer merge-এরই k-pointer সাধারণীকরণ।

কী দিয়ে তথ্য রাখব

একটা min-heap যেখানে প্রতি non-empty list-এর current head node থাকে। node সরাসরি compare করা যায় না (LeetCode-এ), তাই heap-এ (value, tie_breaker, node) রাখি; tie_breaker একটা বাড়তে-থাকা counter, যাতে value সমান হলে heap কখনো node compare না করে।

এটি কেন উপযুক্ত

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

ধাপে ধাপে সমাধান

প্রথম সরল উপায়

প্রথম সরল চিন্তা: সব 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 বানাও

কোথায় বেশি কাজ হচ্ছে

সব 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) হয়, আরও খারাপ।)

যে বিষয়টি খেয়াল করতে হবে

মূল observation: পরের merged node সবসময় k-টা current head-এর মধ্যে smallest। তাই পুরো কিছু sort না করে, শুধু k-টা head একটা heap-এ রাখো; smallest pop করো, merged-এ জোড়ো, সেই list-এর পরের head push করো। heap কখনো k-এর বেশি বড় হয় না।

আরও কম কাজে সমাধান

প্রতিটা 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 করো।

ভাবনার পরিবর্তন

মোচড়: "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)।

ছবিতে বোঝা

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

ছোট input-এ ধাপে ধাপে

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]

কোড ও ব্যাখ্যা

Python

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!")

কোডের প্রতিটি অংশ

• 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 মিলিয়ে দেখা

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

খরচ ও সাধারণ ভুল

সময়

O(N log k) — N = মোট node সংখ্যা, k = list সংখ্যা। প্রতিটা node ঠিক একবার heap-এ ঢোকে আর একবার বেরোয়, আর heap-এ কখনো k-এর বেশি entry থাকে না, তাই প্রতিটা op O(log k)।

অতিরিক্ত জায়গা

O(k) — heap-এ বড়জোর k-টা head entry। output list নতুন node বানায় না (existing node গুলোই re-link করা হয়), তাই extra space heap-টুকুই।

যে ভুলগুলো এড়াতে হবে

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

শেখা ও পরের অনুশীলন

ভিত্তির সঙ্গে সম্পর্ক

ভিত্তি 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)-এর সাথে যমজ।

পরের অনুশীলন

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

কৌশলটি মনে রাখুন

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

নিজেকে যাচাই করুন

ভবিষ্যতের আমাকে: "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।