কনটেন্টে যান

003 — Merge Two Sorted Lists

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

Problem link ও উৎস

  • Original source: Classic capstone interview problem (the merge step of merge sort, on lists)
  • Platform: LeetCode — https://leetcode.com/problems/merge-two-sorted-lists/
  • Topic: linked lists + sorting
  • Difficulty: Easy
  • Pattern: Two-pointer merge with a dummy head
  • Basic idea inherited from: এটা একটা cross-topic capstone — এখানে মেশে 03 linked lists (node-এর next pointer জোড়া দিয়ে list গড়া, dummy head trick) আর sorting ideas (merge sort-এর "merge" ধাপ: দুটো sorted sequence-কে একটা sorted sequence-এ জোড়া)। দুই tool জোড়া লাগলেই এই problem।

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

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

তোমাকে দুটো already sorted (ছোট থেকে বড়) singly linked list দেওয়া আছে। তোমার কাজ: এদের জোড়া দিয়ে একটা নতুন sorted list বানাও, যেখানে দুটো list-এর সব node আছে, এখনও ছোট-থেকে-বড় সাজানো। নতুন list-এর head return করো — পুরনো node গুলোই কাজে লাগাও, value copy কোরো না।

উদাহরণ
list1 : 1 -> 2 -> 4
list2 : 1 -> 3 -> 4
merged: 1 -> 1 -> 2 -> 3 -> 4 -> 4

Input ও output

উদাহরণ
Input : list1 = 1 -> 2 -> 4 ,  list2 = 1 -> 3 -> 4
Output: 1 -> 1 -> 2 -> 3 -> 4 -> 4

Edge case 1 (একটা খালি): list1 = None, list2 = 0 -> Output: 0
Edge case 2 (দুটোই খালি): list1 = None, list2 = None -> Output: None

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

ভাবো দুজন বন্ধু আলাদা আলাদা ভাবে কম-থেকে-বেশি দামে সাজানো বইয়ের দুটো স্তূপ নিয়ে এসেছে। তুমি একটা নতুন তাক ভরছ। প্রতিবার দুই স্তূপের উপরের দুটো বই-এর মধ্যে যেটা সস্তা, সেটা তুলে তাকে রাখো। একটা স্তূপ শেষ হলে অন্যটা পুরোটা পেছনে জুড়ে দাও। তাকটা সাজানো থেকেই যায়।

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

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

এই problem দুটো আগের chapter-এর tool জোড়া দেয়:

  • 03 linked lists থেকে: একটা dummy head বানিয়ে তার পিছনে node জোড়া দেওয়া, আর একটা tail pointer দিয়ে শেষ প্রান্ত ধরে রাখা — list গড়ার ক্লাসিক কৌশল।
  • sorting ideas থেকে: merge sort-এর হৃদয় হলো "merge": দুটো sorted run-এর সামনে দুটো আঙুল রেখে, প্রতিবার ছোটটা তুলে নেওয়া।

একা linked-list জ্ঞান দেয় pointer জোড়া দেওয়ার ক্ষমতা; একা merge-idea দেয় sorted রাখার কৌশল। দুটো মিললে O(m+n)।

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

লুকানো logic একটা invariant: দুটো list যেহেতু sorted, যেকোনো মুহূর্তে দুটো head-এর মধ্যে ছোটটাই হলো বাকি সব node-এর মধ্যে সবচেয়ে ছোট — তাই সেটা নির্দ্বিধায় merged list-এ পরের জায়গায় বসানো যায়। বারবার এই "দুই head-এর ছোটটা তোলো" করলেই output sorted থাকে।

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

কোনো extra বড় structure লাগে না — শুধু একটা dummy head node আর একটা tail pointer, আর দুই input list-এ দুটো reading pointer (a, b)। dummy node (03 linked lists-এর trick) প্রথম node-এর special case ঝামেলা মুছে দেয়।

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

Linked list-এ node গুলো আলাদা আলাদা memory-তে, শুধু next arrow দিয়ে বাঁধা। তাই array-র মতো সরাও-বসাও না করে, আমরা শুধু arrow নতুন করে জুড়ে দিই — tail.next কে ছোট node-এর দিকে তাক করাই। dummy head থাকায় "প্রথম node কোনটা" আলাদা করে ভাবতে হয় না; merge শেষে dummy.next-ই আসল head। এই কারণেই এটা নিখুঁত fit।

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

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

প্রথম সরল চিন্তা: দুটো list-এর সব value একটা array-তে ঢালো, array sort করো, তারপর নতুন list বানাও।

উদাহরণ
1) দুই list -> [1,2,4,1,3,4]
2) sort -> [1,1,2,3,4,4]
3) array থেকে নতুন list গড়ো

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

এটা কাজ করে, কিন্তু input যে already sorted সেই তথ্যটা ফেলে দেয়। আবার sort করা মানে O((m+n) log(m+n)) সময় আর O(m+n) extra array। অথচ দুটো sorted list merge করতে শুধু O(m+n) লাগে আর কোনো নতুন node বানাতেই হয় না — পুরনো node-এর arrow ঘোরালেই হয় (two-way merge idea)।

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

মূল observation: দুটো list sorted বলে, যেকোনো মুহূর্তে পরের সবচেয়ে ছোট element-টা অবশ্যই কোনো-না-কোনো list-এর বর্তমান head। তাই পুরো জিনিস না দেখে, শুধু দুই head তুলনা করলেই পরের সঠিক node পেয়ে যাই। এটাই linear merge সম্ভব করে।

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

একটা dummy head আর tail রাখো। দুই list-এর head a, b তুলনা করো; ছোটটাকে tail.next-এ জুড়ে সেই list-এ এক ঘর এগোও, tail-ও এগোও। একটা list শেষ হলে অন্যটার বাকি অংশ পুরোটা tail.next-এ ঝুলিয়ে দাও (যেহেতু সেটা নিজে sorted)। শেষে dummy.next return করো।

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

মোচড়: "merge করা" ভাবার বদলে ভাবো "দুই head-এর মধ্যে ছোটটা বেছে tail-এ সেলাই করি, একটা শেষ হলে বাকিটা ঝুলিয়ে দিই।" dummy head থাকায় প্রথম node-এর special case-ও মিলিয়ে যায়।

ছবিতে বোঝা

a: 1->2->4, b: 1->3->4 merge করার tail-গড়া:

উদাহরণ
dummy -> ?                a=1  b=1
1<=1 -> tail.next=a(1)     dummy->1            a=2  b=1
1< 2 -> tail.next=b(1)     dummy->1->1         a=2  b=3
2< 3 -> tail.next=a(2)     dummy->1->1->2      a=4  b=3
3< 4 -> tail.next=b(3)     dummy->1->1->2->3   a=4  b=4
4<=4 -> tail.next=a(4)     dummy->1->1->2->3->4           a=N  b=4
b বাকি   -> tail.next=b    dummy->1->1->2->3->4->4           শেষ

head = dummy.next = 1->1->2->3->4->4

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

Input a: 1->3, b: 2:

  1. শুরু: dummy, tail = dummy, a = 1, b = 2
  2. 1 <= 2 → tail.next = a(1); tail এগোলো; a = 3
  3. 3 > 2 → tail.next = b(2); tail এগোলো; b = None
  4. b = None → বাকি a (3) পুরোটা tail.next-এ ঝোলাও
  5. return dummy.next = 1 -> 2 -> 3

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

Python

Python
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def merge_two_lists(a, b):
    dummy = ListNode()          # special-case এড়াতে fake head
    tail = dummy
    while a and b:
        if a.val <= b.val:      # দুই head-এর ছোটটা তোলো
            tail.next = a
            a = a.next
        else:
            tail.next = b
            b = b.next
        tail = tail.next        # tail এক ঘর এগোলো
    tail.next = a if a else b   # যেটা বাকি, পুরোটা ঝোলাও
    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_two_lists(build([1, 2, 4]), build([1, 3, 4]))) == [1, 1, 2, 3, 4, 4]
assert to_list(merge_two_lists(build([]), build([0]))) == [0]            # একটা খালি
assert to_list(merge_two_lists(build([]), build([]))) == []              # দুটোই খালি
assert to_list(merge_two_lists(build([5]), build([1, 2, 3]))) == [1, 2, 3, 5]
print("সব test pass!")

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

  • dummy = ListNode() — একটা fake head, যাতে প্রথম আসল node জোড়ার সময় special case না লাগে (03 linked lists trick)।
  • tail = dummy — tail সবসময় merged list-এর শেষ node ধরে রাখে।
  • while a and b — যতক্ষণ দুটো list-এই node আছে, তুলনা চালাও।
  • if a.val <= b.val — <= রাখায় stable থাকে (সমান হলে a আগে); ছোটটা tail.next-এ জোড়।
  • tail = tail.next — জোড়ার পর tail এক ঘর সামনে।
  • tail.next = a if a else b — একটা list শেষ; বাকিটা যেহেতু নিজে sorted, পুরোটা একবারে ঝুলিয়ে দাও।
  • return dummy.next — আসল head হলো dummy-র পরের node।

Output মিলিয়ে দেখা

[1,2,4] আর [1,3,4] merge করতে tail জুড়ে চলে 1,1,2,3,4, তারপর a-র শেষ 4 ঝুলে যায় → [1,1,2,3,4,4] — assert pass। একটা/দুটো খালি list-ও সঠিক (while চলেই না, বাকিটা ঝুলে যায়)। শেষে print: সব test pass!।

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

সময়

O(m + n) — প্রতিটা node ঠিক একবার করে দেখা ও জোড়া হয়; m, n দুই list-এর দৈর্ঘ্য।

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

O(1) — কোনো নতুন node বানাই না, শুধু arrow ঘোরাই; একটা dummy + কিছু pointer ছাড়া extra memory নেই।

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

  • dummy head না নিয়ে শুরু করা — তখন "প্রথম node কোনটা" নিয়ে আলাদা if-else লাগে, bug বাড়ে।
  • শেষে বাকি অংশ ঝোলাতে ভুলে যাওয়া (tail.next = a if a else b) — তখন লম্বা list-এর লেজ হারিয়ে যায়।
  • < ব্যবহার করে stability হারানো (সমস্যা না হলেও duplicate-এ order বদলায়); <= নিরাপদ।

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

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

ভিত্তি: linked list গড়া (dummy + tail, 03-এর ../../03-linked-list/) + merge sort-এর merge ধাপ (array ও merge-এর পূর্বশর্ত)। দুটো sorted run-কে এক sorted run-এ জোড়ার এই কৌশলই merge sort-এর প্রাণ।

পরের অনুশীলন

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

Two-pointer merge with dummy head: dummy + tail দিয়ে list গড়ে, দুই sorted head-এর ছোটটা বারবার তুলে, শেষে বাকিটা ঝুলিয়ে — O(m+n)-এ দুই sorted list জোড়া। merge sort আর k-way merge-এর building block।

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

ভবিষ্যতের আমাকে: দুটো (বা তার বেশি) sorted জিনিস জোড়ার কথা শুনলেই "dummy head + ছোটটা তোলো + বাকিটা ঝোলাও" মনে করবে। dummy node দিয়ে শুরু করাটাই সবচেয়ে বড় time-saver — first-node special case পুরোপুরি মুছে যায়। এটা চোখ বন্ধ করে লিখতে পারা চাই।

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