কনটেন্টে যান

002 — Merge Two Sorted Lists

Problem link ও উৎস

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

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

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

উদাহরণ
list1: 1 -> 3 -> 5
list2: 2 -> 4 -> 6
ফল  : 1 -> 2 -> 3 -> 4 -> 5 -> 6

Input ও 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

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

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

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

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

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

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

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

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

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

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

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

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

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

সরল চিন্তা: দুই 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

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

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

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

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

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

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

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

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

ছবিতে বোঝা

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

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

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

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

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

Python

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

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

  • 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।

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

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

JavaScript ও test cases

JavaScript
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।

TypeScript ও test cases

TypeScript
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 সেটা নাও" বোঝাই।

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

সময়

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

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

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

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

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

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

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

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

পরের অনুশীলন

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

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

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

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

কোথায় কাজে লাগে

  • 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।