Skip to content

002 — Merge Two Sorted Lists

Source

  • Original source: Classic linked list exercise
  • Platform: LeetCode — https://leetcode.com/problems/merge-two-sorted-lists/
  • Topic: linked list
  • Difficulty: Easy
  • Pattern: merge + dummy head
  • Basic idea inherited from: দুটো sorted জিনিস merge করা (two-pointer merge, ../../02-arrays-and-strings/)

1. Problem in simple words

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

list1: 1 -> 3 -> 5
list2: 2 -> 4 -> 6
ফল  : 1 -> 2 -> 3 -> 4 -> 5 -> 6

2. Which basic idea does this inherit from?

এটা merge sort-এর সেই বিখ্যাত merge step-এরই linked list রূপ — দুটো sorted জিনিস থেকে প্রতিবার ছোট মাথাটা তুলে নেওয়া। array-তে যেটা two-pointer merge (../../02-arrays-and-strings/), এখানে সেটাই pointer দিয়ে।

3. What is the hidden math or logic?

Invariant: যেহেতু দুই list sorted, যেকোনো মুহূর্তে দুই list-এর মাথার ছোটটাই পুরো বাকি সবকিছুর মধ্যে সবচেয়ে ছোট। তাই বারবার দুই মাথা তুলনা করে ছোটটা নিলেই ফল আপনাআপনি sorted থাকে।

4. Which data structure is needed?

কোনো নতুন structure নয় — শুধু একটা dummy head node আর একটা tail pointer। dummy head হলো একটা নকল শুরুর node, যাতে "প্রথম node-টা কে" সেই বিশেষ ক্ষেত্রটা আলাদা করে ভাবতে না হয়।

5. Why this data structure fits

Linked list-এ node যোগ করা মানে শুধু একটা arrow সেট করা — O(1)। dummy head থাকায় আমরা প্রতিটা node-কে একইভাবে tail.next-এ জুড়তে পারি, এমনকি একদম প্রথমটাকেও। এতে edge case (খালি ফল-list) আলাদা করে সামলাতে হয় না — code পরিষ্কার থাকে।

6. Real-life analogy

দুই হাতে দুই গোছা তাস, দুটোই sorted। তুমি নতুন একটা গোছা বানাচ্ছ — প্রতিবার দুই গোছার উপরের তাস দুটো দেখে ছোটটা নতুন গোছায় রাখছ। এক গোছা শেষ হলে বাকিটা পুরো ঢেলে দিচ্ছ।

7. Visual explanation

dummy থেকে শুরু, tail সবসময় ফল-list-এর শেষে:

l1: 1 -> 3 -> 5      l2: 2 -> 4 -> 6
dummy -> ?

1 <= 2 → 1 নাও:   dummy -> 1                  (l1 = 3->5)
3 >  2 → 2 নাও:   dummy -> 1 -> 2             (l2 = 4->6)
3 <= 4 → 3 নাও:   dummy -> 1 -> 2 -> 3        (l1 = 5)
5 >  4 → 4 নাও:   dummy -> 1 -> 2 -> 3 -> 4   (l2 = 6)
5 <= 6 → 5 নাও:   ... -> 5                    (l1 = None)
l1 শেষ → বাকি l2 (6) পুরো জুড়ে দাও: ... -> 5 -> 6

return dummy.next  = 1 -> 2 -> 3 -> 4 -> 5 -> 6

8. Example input and output

Input : l1 = 1 -> 3 -> 5 , l2 = 2 -> 4 -> 6
Output: 1 -> 2 -> 3 -> 4 -> 5 -> 6

Edge 1: l1 = None , l2 = 1 -> 2     -> Output: 1 -> 2
Edge 2: l1 = None , l2 = None       -> Output: None

9. Brute force thinking

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

[1,3,5] + [2,4,6] = [1,3,5,2,4,6] -> sort -> [1,2,3,4,5,6] -> নতুন list

10. Why brute force is slow

দুটো জিনিস already sorted — সেই সুবিধা ফেলে দিয়ে আবার sort করা অপচয় (O(n log n))। তাছাড়া array + নতুন node = O(n) extra space। sorted অবস্থা কাজে লাগালে O(n) সময়ে, পুরোনো node গুলো reuse করেই হয়ে যায়।

11. Key observation

যেহেতু দুটোই sorted, প্রতি মুহূর্তে পরের সঠিক node হলো দুই মাথার ছোটটা — পুরো খোঁজাখুঁজির দরকার নেই, শুধু দুই মাথা তুলনা।

12. Optimized intuition

একটা dummy head বানাও, একটা tail রাখো। যতক্ষণ দুই list-এই node আছে, ছোট-মাথাওয়ালাটা tail-এ জুড়ে সেই list এক ঘর এগিয়ে দাও। একটা শেষ হলে অন্যটার বাকি অংশ সরাসরি tail-এ লাগিয়ে দাও (ওটা তো এমনিতেই sorted)।

13. Thinking tweak

মোচড়: "প্রথম node কোনটা হবে" নিয়ে মাথা না ঘামিয়ে একটা dummy head বসিয়ে দাও — তাহলে সব node একইভাবে জোড়া যায়, শেষে dummy.next ফেরত দিলেই আসল head।

14. Step-by-step dry run

l1 = 1->3, l2 = 2->4:

  1. dummy, tail=dummy
  2. 1 <= 2 → tail.next=1, l1=3, tail=1
  3. 3 > 2 → tail.next=2, l2=4, tail=2
  4. 3 <= 4 → tail.next=3, l1=None, tail=3
  5. l1=None → loop শেষ; tail.next = l2 (4)
  6. return dummy.next = 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):
    dummy = ListNode()      # নকল শুরু — head-এর special case এড়াতে
    tail = dummy
    while l1 and l2:
        if l1.val <= l2.val:
            tail.next = l1  # ছোট মাথাটা জুড়ো
            l1 = l1.next
        else:
            tail.next = l2
            l2 = l2.next
        tail = tail.next    # tail সবসময় শেষে
    tail.next = l1 if l1 else l2   # যেটা বাকি, পুরো জুড়ে দাও
    return dummy.next

# ---- helpers ----
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, 3, 5]), build([2, 4, 6]))) == [1, 2, 3, 4, 5, 6]
assert to_list(merge_two_lists(build([]), build([1, 2]))) == [1, 2]
assert to_list(merge_two_lists(build([]), build([]))) == []
assert to_list(merge_two_lists(build([1, 1]), build([1]))) == [1, 1, 1]  # সমান value
print("সব test pass!")

16. Line-by-line code explanation

  • dummy = ListNode() — নকল head, যাতে প্রথম node-ও সাধারণভাবে জোড়া যায়।
  • tail = dummy — tail সবসময় ফল-list-এর শেষ node।
  • while l1 and l2: — যতক্ষণ দুটোতেই node আছে।
  • if l1.val <= l2.val: — ছোট (বা সমান) মাথাটা বাছো; <= রাখায় stable থাকে।
  • tail.next = ...; ... = ....next — বাছা node জুড়ে, সেই list এগোও।
  • tail = tail.next — tail শেষে সরাও।
  • tail.next = l1 if l1 else l2 — একটা শেষ; বাকিটা already sorted, পুরো জুড়ে দাও।
  • return dummy.next — আসল head।

17. Output walkthrough

[1,3,5] ও [2,4,6] merge হয়ে [1,2,3,4,5,6]। খালি+[1,2] → [1,2]; খালি+খালি → []; [1,1]+[1] → [1,1,1] (সমান value ঠিকভাবে সামলায়)। সব assert pass → সব test pass!।

18. Time complexity

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

19. Space complexity

O(1) — পুরোনো node গুলোই reuse হয়, শুধু dummy + কয়েকটা pointer। (recursive version লিখলে call stack-এ O(n+m) লাগত।)

20. Common mistakes

  • dummy head না নিয়ে head আলাদা করে সামলাতে গিয়ে code জটিল ও bug-প্রবণ হয়ে যায়।
  • শেষে বাকি অংশ (tail.next = l1 if l1 else l2) জুড়তে ভুলে যাওয়া — তখন কিছু node হারায়।
  • < ব্যবহার করা <=-এর বদলে — সমান value-তে সমস্যা না হলেও stable order হারাতে পারে।

21. Which basic problem this inherits from

ভিত্তি: two-pointer merge of two sorted sequences (../../02-arrays-and-strings/patterns.md-এর merge অংশ)। আর dummy-head কৌশল ../patterns.md-তে।

22. Similar harder problems

23. Pattern learned

Merge with dummy head: দুটো sorted chain-কে দুই মাথা তুলনা করে এক পাসে গেঁথে ফেলা; dummy head দিয়ে head-এর special case মুছে দেওয়া।

24. Final summary

ভবিষ্যতের আমাকে: "দুটো sorted list/অংশ এক করতে হলে — dummy head + দুই মাথার ছোটটা বারবার তোলো, একটা শেষ হলে বাকিটা ঢেলে দাও।" Merge sort, k-way merge, add-two-numbers — সবেতেই এই skeleton ফিরে আসবে।

25. JavaScript solution (with test cases)

const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };

class ListNode {
  constructor(val = 0, next = null) { this.val = val; this.next = next; }
}
const arrayToList = (arr) => {
  const dummy = new ListNode();
  let tail = dummy;
  for (const v of arr) { tail.next = new ListNode(v); tail = tail.next; }
  return dummy.next;
};
const listToArray = (head) => {
  const out = [];
  while (head) { out.push(head.val); head = head.next; }
  return out;
};

function mergeTwoLists(l1, l2) {
  const dummy = new ListNode();   // নকল শুরু — head-এর special case এড়াতে
  let tail = dummy;
  while (l1 && l2) {
    if (l1.val <= l2.val) { tail.next = l1; l1 = l1.next; }  // ছোট মাথাটা জুড়ো
    else { tail.next = l2; l2 = l2.next; }
    tail = tail.next;             // tail সবসময় শেষে
  }
  tail.next = l1 || l2;           // যেটা বাকি, পুরো জুড়ে দাও
  return dummy.next;
}

// ---- test cases ----
const eq = (a, b) => JSON.stringify(a) === JSON.stringify(b);
assert(eq(listToArray(mergeTwoLists(arrayToList([1, 3, 5]), arrayToList([2, 4, 6]))), [1, 2, 3, 4, 5, 6]), "main");
assert(eq(listToArray(mergeTwoLists(arrayToList([]), arrayToList([1, 2]))), [1, 2]), "one empty");
assert(eq(listToArray(mergeTwoLists(arrayToList([]), arrayToList([]))), []), "both empty");
assert(eq(listToArray(mergeTwoLists(arrayToList([1, 1]), arrayToList([1]))), [1, 1, 1]), "সমান value");
console.log("সব JS test pass!");

JS টীকা: tail.next = l1 || l2 হলো idiomatic JS — l1 যদি null হয় তবে l2 বসে, কারণ null falsy। dummy head ব্যবহার করায় প্রথম node-ও সাধারণভাবে tail.next-এ জুড়ে যায়, খালি-ফল edge case আলাদা সামলাতে হয় না। <= রাখলে সমান value-তে stable order থাকে। পুরোনো node গুলোই reuse হয়, নতুন node বানানো হয় না — O(1) extra space।

26. TypeScript solution (with test cases)

interface ListNode { val: number; next: ListNode | null }
const node = (val: number, next: ListNode | null = null): ListNode => ({ val, next });

const arrayToList = (arr: number[]): ListNode | null => {
  let head: ListNode | null = null;
  for (let i = arr.length - 1; i >= 0; i--) head = node(arr[i], head);
  return head;
};
const listToArray = (head: ListNode | null): number[] => {
  const out: number[] = [];
  while (head) { out.push(head.val); head = head.next; }
  return out;
};

function mergeTwoLists(l1: ListNode | null, l2: ListNode | null): ListNode | null {
  const dummy: ListNode = node(0);
  let tail: ListNode = dummy;
  while (l1 && l2) {
    if (l1.val <= l2.val) { tail.next = l1; l1 = l1.next; }
    else { tail.next = l2; l2 = l2.next; }
    tail = tail.next;
  }
  tail.next = l1 ?? l2;     // যেটা non-null
  return dummy.next;
}

function expect<T>(a: T, e: T, m = ""): void { if (a !== e) throw new Error(`FAIL ${m}`); }
const S = JSON.stringify;
expect(S(listToArray(mergeTwoLists(arrayToList([1, 3, 5]), arrayToList([2, 4, 6])))), S([1, 2, 3, 4, 5, 6]), "main");
expect(S(listToArray(mergeTwoLists(arrayToList([]), arrayToList([1, 2])))), S([1, 2]), "empty1");
expect(S(listToArray(mergeTwoLists(arrayToList([1, 1]), arrayToList([1])))), S([1, 1, 1]), "dup");
console.log("সব TS test pass!");

TS টীকা: l1 ও l2-কে ListNode | null টাইপ করায় while (l1 && l2)-এর ভেতরে TypeScript narrowing করে দুটোকেই non-null ধরে, তাই l1.val নিরাপদে পড়া যায়। tail কে ListNode (non-null) টাইপ করেছি কারণ dummy থেকে শুরু — কখনো null হয় না। l1 ?? l2 (nullish coalescing) দিয়ে স্পষ্টভাবে "যেটা non-null সেটা নাও" বোঝাই।

27. কোথায় কাজে লাগে (real-world use)

  • Merge sort: linked-list-এর merge sort-এর core merge step ঠিক এই দুই-sorted-list গাঁথা।
  • K-way merge / external sort: বড় sorted file/stream-গুলো একত্র করতে (database, log aggregation) এই দুই-মাথা তুলনার pattern ভিত্তি।
  • Timeline/feed merging: দুটো sorted activity feed (timestamp-ক্রমে) এক feed-এ মেশাতে।
  • Sorted range queries: দুটো sorted index-result merge করে combined result দিতে।
  • Streaming pipelines: দুটো sorted producer থেকে একটা sorted consumer-এ data দিতে।

এক কথায়, দুই (বা বেশি) already-sorted sequence-কে একটা sorted output-এ গাঁথতে হলে dummy-head + দুই-মাথা তুলনা skeleton-ই সবচেয়ে পরিষ্কার ও O(n) সমাধান।

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