3.2 Dummy Node Technique

Demo: Merge Two Sorted Lists — LC 21 (Easy — Amazon/Meta/Google High)

Statement (Demo): দুটো sorted linked list list1 ও list2-এর head দেওয়া — দুটোকে একটা sorted linked list-এ merge করে তার head return করুন। উদাহরণ: list1=[1,2,4], list2=[1,3,4] → [1,1,2,3,4,4] | ⚡ n,m ≤ 50

Approach: dummy থেকে tail চালান; দুই লিস্টের ছোট নোডটা tail-এ জুড়ুন। একটা শেষ হলে অন্যটার বাকি অংশ সরাসরি জুড়ে দিন।

function mergeTwoLists(a, b) {
  const dummy = { next: null };
  let tail = dummy;
  while (a && b) {
    if (a.val <= b.val) {
      tail.next = a;
      a = a.next;
    } else {
      tail.next = b;
      b = b.next;
    }
    tail = tail.next;
  }
  tail.next = a || b;
  return dummy.next;
}

Complexity: Time O(m+n), Space O(1)