Tarkibga o'tish

Ikki listni birlashtirish

Ikkita navbatni tasavvur qiling: har birida odamlar bo‘y bo‘yicha o‘sish tartibida turibdi. Ikkala navbatni bitta navbatga, baribir bo‘y bo‘yicha o‘sish tartibini buzmasdan qo‘shish kerak. Buning uchun ikkala navbatning oldingi odamlarini solishtirib, qaysi biri pastroq bo‘lsa, uni yangi navbatga chiqarib qo‘yish, so‘ng shu navbatda keyingi odamga o‘tish kifoya. Ikkita saralangan linked listni birlashtirish ham xuddi shu mantiqqa asoslanadi.

Masala sharti

Ikkita saralangan singly linked list berilgan — list1 va list2. Ularni bitta saralangan linked listga birlashtirish kerak, natijada barcha elementlar o‘sish tartibida bo‘lishi kerak.

list1:  1 → 3 → 5 → NULL
list2:  2 → 4 → 6 → NULL

Natija: 1 → 2 → 3 → 4 → 5 → 6 → NULL

Ikkala ro‘yxat ham allaqachon saralangan deb faraz qilinadi — bu masalaning asosiy sharti. Agar ro‘yxatlar saralanmagan bo‘lsa, quyidagi yechim ishlamaydi; bu holda avval har ikkalasini alohida saralash kerak bo‘lardi.

Nega yangi ro‘yxat yaratishga ehtiyoj yo‘q?

Arraylarni birlashtirishda odatda natija uchun yangi massiv ajratiladi, chunki ikkala manba arrayni ham o‘zgartirmasdan qoldirish qulay. Linked listda esa mavjud node’larni qayta ishlatish mumkin: kerak bo‘lgani — ularning next bog‘lanishlarini qayta yo‘naltirish, xolos. Bu qiymatlarni ko‘chirishdan qochish imkonini beradi.

Optimal yechim: sentinel node bilan ikki ko‘rsatkichli birlashtirish

G‘oya: list1 va list2 bo‘ylab bir vaqtda ikkita reference yuritamiz. Har qadamda ularning joriy qiymatlarini solishtiramiz, kichigini natija ro‘yxatiga ulaymiz va o‘sha ro‘yxatda keyingi node’ga o‘tamiz. Natija ro‘yxatini qurishni osonlashtirish uchun sentinel (dummy) node ishlatiladi — bu haqiqiy qiymat saqlamaydigan, faqat boshlang‘ich nuqta vazifasini bajaradigan yordamchi node.

FUNCTION MERGE_TWO_SORTED(list1, list2)
    sentinel = NEW NODE(HECH_QANDAY_QIYMAT)
    tail = sentinel

    WHILE list1 != NULL AND list2 != NULL
        IF list1.value <= list2.value
            tail.next = list1
            list1 = list1.next
        ELSE
            tail.next = list2
            list2 = list2.next

        tail = tail.next

    // ikkalasidan biri tugadi, qolgan qismini to'g'ridan-to'g'ri ulaymiz
    IF list1 != NULL
        tail.next = list1
    ELSE
        tail.next = list2

    RETURN sentinel.next

Sentinel node’siz ham yozish mumkin, ammo u holda “natija ro‘yxatining birinchi node’i hali tanlanmagan” degan alohida holatni maxsus tekshirish kerak bo‘lardi. Sentinel bu holatni yo‘qotadi: tail boshida sentinelni ko‘rsatadi, va birinchi haqiqiy node ulanganda sentinel.next avtomatik ravishda natijaning boshiga aylanadi.

Bosqichma-bosqich misol

list1: 1 → 3 → 5 → NULL, list2: 2 → 4 → NULL.

Boshlanish:
sentinel → NULL
tail = sentinel
list1 = 1, list2 = 2


1-qadam: 1 <= 2  → sentinel dan keyin 1 ulanadi
sentinel → 1
tail = 1,  list1 = 3, list2 = 2


2-qadam: 3 > 2  → keyin 2 ulanadi
sentinel → 1 → 2
tail = 2,  list1 = 3, list2 = 4


3-qadam: 3 <= 4  → keyin 3 ulanadi
sentinel → 1 → 2 → 3
tail = 3,  list1 = 5, list2 = 4


4-qadam: 5 > 4  → keyin 4 ulanadi
sentinel → 1 → 2 → 3 → 4
tail = 4,  list1 = 5, list2 = NULL


list2 = NULL bo'lgani uchun sikl to'xtaydi.
Qolgan list1 (5 → NULL) to'g'ridan-to'g'ri ulanadi:

sentinel → 1 → 2 → 3 → 4 → 5 → NULL

Natija: sentinel.next, ya'ni 1 → 2 → 3 → 4 → 5 → NULL

Ikkala ro‘yxatning node’lari ham qayta yaratilmadi — ular faqat qayta ulandi. Yagona yangi node — sentinel — va u yakuniy natijaga kirmaydi, faqat qurilish jarayonida yordamchi vazifasini bajaradi.

Nega bu ishlaydi?

Sikl invarianti: har bir iteratsiya boshlanishida sentineldan tailgacha bo‘lgan zanjir — hozirgacha ko‘rilgan barcha elementlarning saralangan birlashmasidir. Har qadamda list1 va list2ning joriy elementlaridan kichigi tanlanadi. Ikkala manba ro‘yxat ham allaqachon saralangan bo‘lgani uchun, har bir ro‘yxatning joriy elementi o‘sha ro‘yxatdagi eng kichik ko‘rilmagan qiymatdir. Demak, ikkalasining orasidan eng kichigini tanlash — butun ikki ro‘yxat bo‘yicha ham hali ko‘rilmagan eng kichik qiymatni tanlash bilan barobar. Sikl tugagach, bir ro‘yxat tugaydi; qolgan ro‘yxat esa allaqachon saralangan va uning barcha elementlari ikkinchi ro‘yxatning oxirgi ulangan elementidan katta yoki teng bo‘lishi kafolatlangan, shuning uchun uni o‘zgartirmasdan to‘g‘ridan-to‘g‘ri ulash mumkin.

Vaqt va xotira murakkabligi

Har bir iteratsiyada ikkala ro‘yxatdan birida bitta node “iste’mol qilinadi”. list1da m, list2da n ta node bo‘lsa, sikl umumiy holda ko‘pi bilan m + n marta bajariladi, keyin qolgan qism bitta O(1) ulanish bilan qo‘shiladi. Shuning uchun vaqt murakkabligi O(m + n).

Yordamchi xotira — faqat sentinel node va bir nechta reference (tail, va list1, list2ning o‘zi). Yangi qiymat node’lari yaratilmaydi, mavjudlari qayta ulanadi, shuning uchun qo‘shimcha xotira murakkabligi O(1) (sentinel uchun bitta qo‘shimcha node hisobga olinmasa ham, natijaga ta’siri doimiy).

Rekursiv variant

FUNCTION MERGE_RECURSIVE(list1, list2)
    IF list1 = NULL
        RETURN list2

    IF list2 = NULL
        RETURN list1

    IF list1.value <= list2.value
        list1.next = MERGE_RECURSIVE(list1.next, list2)
        RETURN list1
    ELSE
        list2.next = MERGE_RECURSIVE(list1, list2.next)
        RETURN list2

Vaqt murakkabligi baribir O(m + n). Ammo har bir chaqiruv call stackda joy egallagani uchun qo‘shimcha xotira O(m + n) bo‘ladi — iterativ variantdagi O(1)dan farqli o‘laroq. Juda uzun ro‘yxatlarda bu stack chegarasidan oshib ketishi mumkin.

Nozik holatlar

  • Bitta ro‘yxat bo‘sh. list1 = NULL bo‘lsa, sikl darhol to‘xtaydi va list2ning o‘zi to‘liq natija bo‘lib qoladi (yoki aksincha).
  • Ikkala ro‘yxat ham bo‘sh. Sikl bajarilmaydi, so‘ngra ham list1, ham list2 NULL bo‘lgani uchun tail.next = NULL bo‘lib qoladi — natija bo‘sh ro‘yxat, bu to‘g‘ri.
  • Teng qiymatlar. list1.value <= list2.value sharti <= (kattaroq yoki teng emas, balki kichikroq yoki teng) ishlatgani uchun, qiymatlar teng bo‘lganda list1dagi element birinchi ulanadi. Bu tanlov ixtiyoriy, ammo izchil bo‘lishi kerak — aks holda barqaror birlashtirish (stable merge) xususiyati yo‘qoladi, ya’ni teng qiymatlarning original nisbiy tartibi buzilishi mumkin.
  • Ro‘yxatlar turli uzunlikda. Sikldan keyin qolgan qism har doim to‘g‘ri ulanadi, chunki list1 yoki list2dan faqat biri NULL bo‘lishi mumkin — ikkalasi bir vaqtda tugasa ham, qolgan qism shunchaki NULL bo‘ladi.

Keng tarqalgan xatolar

Manba ro‘yxatlar saralanmagan deb noto‘g‘ri faraz qilish. Algoritm faqat ikkala ro‘yxat ham oldindan saralangan bo‘lganda to‘g‘ri natija beradi. Saralanmagan ro‘yxatlarda bu usul ishlamaydi — chunki har bir ro‘yxatning “joriy elementi” endi o‘sha ro‘yxatdagi eng kichik ko‘rilmagan qiymat degani emas.

Sentinelni natijaga qo‘shib yuborish. Funksiya sentinel.nextni emas, sentinelning o‘zini qaytarsa, natija ro‘yxatining boshida haqiqiy bo‘lmagan qo‘shimcha node paydo bo‘ladi.

Qolgan qismni unutib, faqat sikl bilan cheklanish. Agar sikldan keyin qolgan list1 yoki list2ni ulash qadami tashlab ketilsa, uzunroq ro‘yxatning qolgan qismi natijaga umuman kirmay qoladi.

Qiymatlarni ko‘chirib, yangi node’lar yaratish. Bu texnik jihatdan noto‘g‘ri emas, lekin keraksiz — mavjud node’larni qayta ulash yetarli bo‘lgan joyda yangi xotira ajratish ortiqcha ish va ortiqcha xotira sarflaydi.

Xulosa

Ikkita saralangan linked listni birlashtirish — ikkita ko‘rsatkichni parallel yuritish va har qadamda kichik qiymatni tanlash g‘oyasiga asoslanadi, xuddi ikki navbatni birlashtirishga o‘xshab. Sentinel node natija ro‘yxatini qurishni soddalashtiradi, chekka holatlarni alohida tekshirish shart qilmaydi. Bu yondashuv keyinchalik ko‘proq ro‘yxatni birlashtirishga (masalan, merge sort algoritmining asosiy qadami sifatida) tabiiy ravishda kengaytiriladi.