Skip to content

003 — Merge Two Sorted Lists

Source

  • 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 — এখানে মেশে 04 linked lists (node-এর next pointer জোড়া দিয়ে list গড়া, dummy head trick) আর 03 sorting ideas (merge sort-এর "merge" ধাপ: দুটো sorted sequence-কে একটা sorted sequence-এ জোড়া)। দুই tool জোড়া লাগলেই এই problem।

1. Problem in simple words

তোমাকে দুটো 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

2. Which basic idea does this inherit from?

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

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

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

3. What is the hidden math or logic?

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

4. Which data structure is needed?

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

5. Why this data structure fits

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

6. Real-life analogy

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

7. Visual explanation

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)     ...->3->4           a=N  b=4
b বাকি   -> tail.next=b    ...->4->4           শেষ

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

8. Example input and 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

9. Brute force thinking

প্রথম সরল চিন্তা: দুটো 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 গড়ো

10. Why brute force is slow

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

11. Key observation

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

12. Optimized intuition

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

13. Thinking tweak

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

14. Step-by-step dry run

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

15. Python solution

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

16. Line-by-line code explanation

  • dummy = ListNode() — একটা fake head, যাতে প্রথম আসল node জোড়ার সময় special case না লাগে (04 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।

17. Output walkthrough

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

18. Time complexity

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

19. Space complexity

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

20. Common mistakes

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

21. Which basic problem this inherits from

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

22. Similar harder problems

23. Pattern learned

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

24. Final summary

ভবিষ্যতের আমাকে: দুটো (বা তার বেশি) 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।