Skip to content

006 — Merge Two Sorted Lists

Source

  • Original source: Classic linked-list / recursion exercise
  • Platform: LeetCode — https://leetcode.com/problems/merge-two-sorted-lists/
  • Topic: recursion (decrease-and-conquer on lists)
  • Difficulty: Easy
  • Pattern: decrease-and-conquer — ছোট head বেছে বাকিটা recursively merge
  • Basic idea inherited from: linked lists section + leap of faith

1. Problem in simple words

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

list1 : 1 -> 2 -> 4
list2 : 1 -> 3 -> 4
merge : 1 -> 1 -> 2 -> 3 -> 4 -> 4

2. Which basic idea does this inherit from?

ভিত্তি হলো linked lists section + leap of faith। দুটো sorted list-এর মধ্যে যেটার head ছোট, সেটাই পুরো merged list-এর head হবে — এটা নিশ্চিত। তারপর সেই head-এর next-এ বসবে "বাকি অংশ আর অন্য list-এর merge"। ওই বাকি merge-টা recursion-কে বিশ্বাস করে দিয়ে দাও (leap of faith); নিজে ভেতরে ঢুকে trace কোরো না।

3. What is the hidden math or logic?

লুকানো logic একটা invariant: যেকোনো মুহূর্তে দুই list-এর দুই head-ই নিজ নিজ list-এর সবচেয়ে ছোট অবশিষ্ট element। তাই ওই দুইয়ের মধ্যে ছোটটাই গোটা অবশিষ্ট merge-এর সবচেয়ে ছোট element — সেটাকে সামনে বসিয়ে বাকি problem এক node ছোট করে দাও। প্রতি step-এ ঠিক একটা node স্থায়ীভাবে জায়গা পায়।

4. Which data structure is needed?

Linked list নিজেই — নতুন কোনো structure লাগে না। আমরা শুধু বিদ্যমান node-গুলোর next pointer আবার বাঁধি (rewire), নতুন node বানাই না। recursion-এর জন্য call stack লাগে।

5. Why this data structure fits

Linked list-এ একটা node-কে অন্যটার সামনে জোড়া দেওয়া মানে শুধু একটা next pointer বদলানো — O(1)। array হলে মাঝখানে ঢোকাতে shift করতে হতো (O(n))। যেহেতু merge মানে বারবার "ছোট head-টা সামনে আনো", linked list-এর সস্তা pointer-rewiring এটাকে নিখুঁতভাবে মানায়, কোনো বাড়তি memory ছাড়াই।

6. Real-life analogy

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

7. Visual explanation

প্রতি call ছোট head বেছে বাকিটার merge-কে তার next-এ বসায় — single chain, গভীরতা = মোট node সংখ্যা:

merge(1a->2->4 , 1b->3->4)
  1a <= 1b -> 1a.next = merge(2->4 , 1b->3->4)
       1b < 2 -> 1b.next = merge(2->4 , 3->4)
            2 < 3 -> 2.next = merge(4 , 3->4)
                 3 < 4 -> 3.next = merge(4 , 4)
                      4 <= 4 -> 4a.next = merge(None , 4)
                           list1 None -> return list2 (4)   [base case]
ফলাফল গাঁথা: 1a -> 1b -> 2 -> 3 -> 4a -> 4

8. Example input and output

Input : 1->2->4 , 1->3->4 -> Output: 1->1->2->3->4->4
Input : 5       , 1->2->3  -> Output: 1->2->3->5

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

9. Brute force thinking

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

1) দুই list ঘুরে -> [1,2,4,1,3,4]
2) sort -> [1,1,2,3,4,4]
3) নতুন list বানাও

10. Why brute force is slow

কাজ করে, কিন্তু দুটো অপচয়: (a) array sort করতে O(m+n log(m+n)), অথচ input তো আগেই sorted — এই তথ্য নষ্ট হলো; (b) O(m+n) extra space (array + নতুন node)। অথচ দুই head তুলনা করেই linear সময়ে, পুরোনো node গুলো rewire করে, কম জায়গায় merge করা যায়।

11. Key observation

মূল observation: দুই sorted head-এর মধ্যে ছোটটাই merged list-এর পরের element — এর চেয়ে ছোট আর কিছু কোনো list-এ নেই। তাই পুরো list একসাথে না ভেবে, শুধু "এই মুহূর্তে কোন head ছোট" ঠিক করো, সেটা বসাও, বাকিটা recursion-কে দাও।

12. Optimized intuition

Base case: কোনো list None হলে অন্যটা যেমন আছে তেমন ফেরত দাও (sorted তো বটেই)। নাহলে দুই head তুলনা করো; ছোট head-টা রাখো, তার next-এ বসাও "ওই head বাদ দিয়ে বাকি অংশ আর অন্য list-এর merge"। সেই ছোট head-ই এই level-এর উত্তর। leap of faith: ভেতরের merge ঠিক করবে — তুমি শুধু এই এক জোড়া তুলনা সামলাও।

13. Thinking tweak

মোচড়: "দুটো পুরো list কীভাবে মেশাব?" ভাবার বদলে জিজ্ঞেস করো "merged list-এর সবচেয়ে প্রথম node-টা কে?" — অবশ্যই দুই head-এর ছোটটা। ওটা বসিয়ে দিলে বাকি কাজটা ঠিক একই ধরনের, এক node ছোট problem; recursion-কে বিশ্বাস করো।

14. Step-by-step dry run

merge(1->3, 2->4):

  1. 1 <= 2 → head = node 1; 1.next = merge(3, 2->4)।
  2. 3 > 2 → head = node 2; 2.next = merge(3, 4)।
  3. 3 <= 4 → head = node 3; 3.next = merge(None, 4)।
  4. list1 None → base case, return 4।
  5. unwind করে গাঁথা হয়: 1 -> 2 -> 3 -> 4।

15. Python solution

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

def merge_two_lists(l1, l2):
    if l1 is None:          # base case: এক list শেষ
        return l2
    if l2 is None:
        return l1
    if l1.val <= l2.val:    # ছোট head বেছে নাও
        l1.next = merge_two_lists(l1.next, l2)
        return l1
    else:
        l2.next = merge_two_lists(l1, l2.next)
        return l2

# ---- 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([5]), build([1, 2, 3]))) == [1, 2, 3, 5]
assert to_list(merge_two_lists(build([]), build([]))) == []       # দুটোই খালি
assert to_list(merge_two_lists(build([]), build([0, 1]))) == [0, 1]  # একটা খালি
assert to_list(merge_two_lists(build([1, 1]), build([1, 1]))) == [1, 1, 1, 1]  # সব সমান
print("সব test pass!")

16. Line-by-line code explanation

  • if l1 is None: return l2 / if l2 is None: return l1 — base case: এক list ফুরালে বাকিটা পুরোটা জুড়ে দাও।
  • if l1.val <= l2.val: — দুই head তুলনা; <= রাখায় সমান হলে stable থাকে।
  • l1.next = merge_two_lists(l1.next, l2) — l1-এর head রেখে তার পরের অংশ ও l2-কে merge করে পেছনে জোড়া।
  • return l1 / return l2 — যে head ছোট, সেটাই এই level-এর merged head।

17. Output walkthrough

merge_two_lists(build([1,2,4]), build([1,3,4])): প্রতি ধাপে ছোট head বসে — 1,1,2,3,4,4 গাঁথা হয়, to_list দেয় [1,1,2,3,4,4]। [5] ও [1,2,3]-এ 5 শেষে বসে। দুটো খালি → None → []। এক খালি → অন্যটা সরাসরি। সব-সমান case-ও ঠিক, তারপর print: সব test pass!।

18. Time complexity

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

19. Space complexity

O(m + n) recursion stack-এর জন্য (প্রতি node-এ এক level গভীর)। Iterative version-এ O(1) — নতুন node বানে না, শুধু pointer rewire।

20. Common mistakes

  • base case (এক list None) না রাখা — None.val-এ crash।
  • < ব্যবহার করে সমান value-তে stability নষ্ট করা; <= নিরাপদ।
  • recursion-এর ফল next-এ assign করতে ভুলে যাওয়া — তখন বাকি অংশ হারিয়ে যায়।
  • নতুন node বানিয়ে memory নষ্ট করা — পুরোনো node rewire করলেই হয়।
  • Python-এ খুব লম্বা list-এ depth limit — তখন iterative দুই-pointer version বেছে নাও।

21. Which basic problem this inherits from

ভিত্তি: linked-list traversal (../../03-linked-list/) + leap of faith (../concept.md)। এটাই Merge Sort-এর combine step; ../patterns.md-এর Pattern 1 (decrease-and-conquer) দেখো। আটকে গেলে আগে Reverse Linked List (../../03-linked-list/problems/001-reverse-linked-list.md) ঝালিয়ে নাও।

22. Similar harder problems

23. Pattern learned

Decrease-and-conquer on lists: দুই head তুলনা করে ছোটটা সামনে বসাও, বাকিটার merge তার next-এ recursively গাঁথো — merge sort ও যেকোনো "দুই sorted ধারা মেশানো" কাজের মূল pattern।

24. Final summary

ভবিষ্যতের আমাকে: "Merge = ছোট head বেছে নাও, তার next-এ বাকিটার merge বসাও; এক list শেষ হলে অন্যটা জুড়ে দাও।" যখনই দুটো (বা k-টা) sorted ধারা একত্র করতে হবে — এই two-head compare + leap-of-faith recursion মনে করবে।

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