Tarkibga o'tish

Palindrom linked list

“Aftob”, “abba”, “12321” — bu ketma-ketliklar oldindan o‘qilsa ham, orqadan o‘qilsa ham bir xil ko‘rinadi. Bunday xususiyatga ega ketma-ketlik palindrom deb ataladi. String yoki arrayda buni tekshirish oson: boshidagi va oxiridagi indexlarni bir-biriga solishtirib, o‘rtaga qarab yaqinlashtirish kifoya. Linked listda esa oxiridan boshlab index orqali element olib bo‘lmaydi — bu masalani nafaqat mantiqiy, balki texnik jihatdan ham qiziqarli qiladi.

Masala sharti

Bosh (head) reference’i berilgan singly linked list mavjud. Ro‘yxatdagi qiymatlar ketma-ketligi palindrom ekanligini, ya’ni uni oldindan o‘qish bilan orqadan o‘qish natijasi bir xil ekanligini tekshirish kerak.

Kirish:  1 → 2 → 3 → 2 → 1 → NULL
Chiqish: TO'G'RI (palindrom)

Kirish:  1 → 2 → 3 → NULL
Chiqish: NOTO'G'RI

Kirish:  (bo'sh ro'yxat)
Chiqish: TO'G'RI (bo'sh ketma-ketlik palindrom hisoblanadi)

Sodda yechim: qiymatlarni alohida tuzilmaga ko‘chirish

Eng oddiy yo‘l — ro‘yxat bo‘ylab bir marta yurib, barcha qiymatlarni dynamic array’ga ko‘chirish, so‘ng shu array ustida ikki ko‘rsatkichli klassik palindrom tekshiruvini bajarish:

FUNCTION IS_PALINDROME_WITH_ARRAY(head)
    values = BO'SH DYNAMIC ARRAY
    current = head

    WHILE current != NULL
        values.PUSH(current.value)
        current = current.next

    left = 0
    right = values.length - 1

    WHILE left < right
        IF values[left] != values[right]
            RETURN NOTO'G'RI
        left = left + 1
        right = right - 1

    RETURN TO'G'RI

Bu yechim to‘g‘ri ishlaydi va vaqt murakkabligi O(n), ammo n ta qiymatni saqlash uchun O(n) qo‘shimcha xotira talab qiladi. Linked listning o‘zi allaqachon O(n) xotira egallayotgan bo‘lsa-da, ko‘p vaziyatlarda qo‘shimcha O(n) xotirasiz yechim topish maqsad qilinadi — ayniqsa ro‘yxat juda katta bo‘lsa.

Optimal yechim: o‘rtani topish, ikkinchi yarmni teskari aylantirish, solishtirish

G‘oya uchta oldin ko‘rilgan texnikani ketma-ket birlashtiradi:

  1. Fast-slow pointer yordamida ro‘yxatning o‘rtasini topamiz (qarang: o‘rtasini topish).
  2. Ro‘yxatning ikkinchi yarmini teskari aylantiramiz (qarang: teskari qilish).
  3. Birinchi yarmni va teskari aylantirilgan ikkinchi yarmni bir vaqtda oldinga yurib solishtiramiz.
FUNCTION IS_PALINDROME(head)
    IF head = NULL OR head.next = NULL
        RETURN TO'G'RI

    // 1. O'rtani topish
    slow = head
    fast = head

    WHILE fast.next != NULL AND fast.next.next != NULL
        slow = slow.next
        fast = fast.next.next

    // 2. Ikkinchi yarmni teskari aylantirish
    second_half = REVERSE(slow.next)

    // 3. Ikkala yarmni solishtirish
    first_pointer = head
    second_pointer = second_half
    result = TO'G'RI

    WHILE second_pointer != NULL
        IF first_pointer.value != second_pointer.value
            result = NOTO'G'RI
            BREAK
        first_pointer = first_pointer.next
        second_pointer = second_pointer.next

    // 4. Ro'yxatni asl holatiga qaytarish (ixtiyoriy, lekin yaxshi amaliyot)
    slow.next = REVERSE(second_half)

    RETURN result

REVERSE funksiyasi — teskari qilish maqolasida ko‘rilgan xuddi shu uchta ko‘rsatkichli algoritm.

Bosqichma-bosqich misol

Kirish: 1 → 2 → 3 → 2 → 1 → NULL.

1-qadam: o'rtani topish (fast-slow pointer)

slow = 1, fast = 1
1-siljish: slow = 2, fast = 3
2-siljish: slow = 3, fast = 5   (fast.next = NULL bo'lgani uchun sikl to'xtaydi)

slow = 3   (o'rtadagi node)


2-qadam: ikkinchi yarmni teskari aylantirish

slow.next, ya'ni  2 → 1 → NULL   teskari aylantiriladi:

second_half = 1 → 2 → NULL


3-qadam: solishtirish

Birinchi yarm:   1 → 2 → 3 → ...
Ikkinchi yarm:   1 → 2 → NULL

first_pointer  = 1,  second_pointer = 1   →  teng
first_pointer  = 2,  second_pointer = 2   →  teng

second_pointer = NULL  →  sikl to'xtaydi, result = TO'G'RI

Diqqat qiling: second_halfda faqat ikkita element bor (1 → 2), o‘rtadagi 3 esa taqqoslashda ishtirok etmaydi. Bu to‘g‘ri, chunki toq uzunlikdagi palindromda o‘rtadagi element o‘zi bilan o‘zini solishtirishga muhtoj emas — u avtomatik ravishda mos keladi.

Nega bu ishlaydi?

Palindromning ta’rifiga ko‘ra, ketma-ketlikning birinchi yarmi ikkinchi yarmning teskarisiga teng bo‘lishi kerak (o‘rtadagi elementni, agar uzunlik toq bo‘lsa, hisobga olmaganda). Ikkinchi yarmni teskari aylantirib, uni birinchi yarm bilan boshidan boshlab solishtirish aynan shu ta’rifni tekshiradi: agar ikkala yarim — biri to‘g‘ri, biri teskari aylantirilgan holda — elementma-element bir xil bo‘lsa, demak asl ketma-ketlik palindrom.

O‘rtani aniq topish uchun ishlatilgan fast-slow pointer sharti (fast.next != NULL AND fast.next.next != NULL) juft va toq uzunlikdagi ro‘yxatlarda slowni ikkinchi yarmning boshidan bitta oldingi node’da to‘xtatadi — shu sababli slow.next aynan ikkinchi yarmning boshlanishi bo‘ladi.

Vaqt va xotira murakkabligi

Uchta bosqichning har biri ro‘yxatning taxminan yarmi yoki to‘liq uzunligi bo‘ylab bitta o‘tishni talab qiladi: o‘rtani topish O(n), teskari aylantirish O(n/2), solishtirish O(n/2), va (ixtiyoriy) asl holatga qaytarish yana O(n/2). Bularning yig‘indisi baribir O(n) bo‘lib qoladi, chunki doimiy ko‘paytuvchilar Big O notatsiyasida hisobga olinmaydi.

Yordamchi xotira esa bir nechta reference (slow, fast, first_pointer, second_pointer) bilan cheklanadi — yangi tuzilma yoki massiv yaratilmaydi, faqat mavjud node’larning next bog‘lanishlari vaqtincha o‘zgartiriladi. Shuning uchun xotira murakkabligi O(1) — bu sodda, array asosidagi yechimdan ustunligi.

Bu yerda muhim savol tug‘iladi: nega O(n) xotira sarflaydigan array yechimi ba’zan afzal ko‘riladi? Chunki optimal yechim ro‘yxatni vaqtincha o‘zgartiradi (ikkinchi yarmni teskari aylantiradi). Agar ro‘yxat boshqa joyda bir vaqtning o‘zida o‘qilayotgan bo‘lsa (masalan, parallel ishlov berishda) yoki ro‘yxatni o‘zgarishsiz qoldirish qat’iy talab qilinsa, array asosidagi yechim xavfsizroq bo‘lishi mumkin — garchi u ko‘proq xotira sarflasa ham.

Nozik holatlar

  • Bo‘sh ro‘yxat. Ta’rifga ko‘ra bo‘sh ketma-ketlik palindrom hisoblanadi, shuning uchun funksiya darhol TO'G'RI qaytaradi.
  • Bitta elementli ro‘yxat. Yagona element o‘zi bilan o‘zi mos keladi, natija har doim TO'G'RI.
  • Ikkita elementli ro‘yxat. Ular teng bo‘lsa palindrom (5 → 5), teng bo‘lmasa emas (5 → 3). O‘rtani topish algoritmida slow birinchi elementda to‘xtaydi, slow.next esa ikkinchi elementdan boshlanadigan “ikkinchi yarim” bo‘ladi.
  • Toq va juft uzunlik. Yuqorida ko‘rsatilganidek, toq uzunlikda o‘rtadagi element solishtirishda ishtirok etmaydi; bu algoritm to‘g‘ri ishlashi uchun zarur, chunki uni ikki tomonga ham tegishli deb hisoblash mumkin emas.

Keng tarqalgan xatolar

Ro‘yxatni asl holatiga qaytarishni unutish. Agar chaqiruvchi kod funksiyadan keyin ham ro‘yxatdan foydalanishi kerak bo‘lsa-yu, ikkinchi yarm teskari aylantirilgan holicha qoldirilsa, ro‘yxatning tuzilishi buziladi. Bu qadam masala sharti “ro‘yxatni o‘zgartirmang” demasa ham, yaxshi amaliyot hisoblanadi.

O‘rtani noto‘g‘ri aniqlash. Fast-slow pointer sharti biroz farq qilsa (masalan, fast != NULL o‘rniga fast.next != NULL ishlatilsa), slow boshqa node’da to‘xtashi va ikkinchi yarm chegarasi noto‘g‘ri belgilanishi mumkin — bu ayniqsa juft uzunlikdagi ro‘yxatlarda natijani noto‘g‘ri chiqarishi mumkin.

Faqat qiymatlarni emas, reference’larni solishtirish. Solishtirish bosqichida first_pointer.value != second_pointer.value o‘rniga xato bilan first_pointer != second_pointer yozilsa, ikkita turli node har doim teng bo‘lmagan deb hisoblanadi, garchi ularning qiymatlari bir xil bo‘lsa ham.

Xulosa

Palindrom linked list masalasi o‘ziga xos yangi algoritm emas — u avval ko‘rilgan uchta texnikani (o‘rtani topish, teskari aylantirish, ikki ko‘rsatkichli solishtirish) ketma-ket birlashtirish orqali yechiladi. Bu shuni ko‘rsatadiki, linked list bilan ishlashda murakkab masalalar ko‘pincha bir nechta sodda, izchil g‘oyalarning tabiiy davomidan iborat bo‘ladi — har birini alohida tushunish, keyin ularni to‘g‘ri tartibda birlashtirish yetarli.