Tsikl bormi?

Tog‘li piyodalar yo‘lini tasavvur qiling: ba’zi yo‘llar to‘g‘ri chiziq bo‘ylab manzilga olib boradi, ba’zilari esa aylanma bo‘lib, siz bilmagan holda yana avvalgi nuqtaga qaytarib qo‘yadi. Agar xaritangiz bo‘lmasa, faqat yo‘l bo‘ylab yurib, qaysi holatda ekaningizni qanday bilasiz? Linked list bilan ham xuddi shu muammo yuzaga kelishi mumkin: node’lardan biri, NULL bilan tugash o‘rniga, orqadagi biror node’ga qaytadan ulanib qolgan bo‘lishi mumkin.

Masala sharti

Bosh (head) reference’i berilgan singly linked list mavjud. Ro‘yxat ichida tsikl — ya’ni biror node’ning next bog‘lanishi orqaga, avval ko‘rilgan biror node’ga qaytadan olib boradigan holat — bor-yo‘qligini aniqlash kerak.

Tsiklsiz:  1 → 2 → 3 → 4 → NULL

Tsiklli:   1 → 2 → 3 → 4
                   ↑         |
                   └─────────┘

Tsiklli ro‘yxatda oddiy traversal (WHILE current != NULL) hech qachon NULLga yetmaydi va cheksiz davom etadi. Shu sababli tsiklni aniqlash ma’lumotlar tuzilmasining ichki bog‘lanishlari ustida to‘g‘ridan-to‘g‘ri fikrlashni talab qiladi, oddiy ko‘rib chiqish yetarli emas.

Nega node’larni “belgilab” bo‘lmaydi?

Ba’zan birinchi fikr — har bir ko‘rilgan node’ni belgilab qo‘yish, so‘ng belgilangan node’ga qayta duch kelinsa, tsikl bor deb xulosa chiqarish. Bu ishlaydi, ammo node strukturasiga qo‘shimcha maydon qo‘shishni yoki har bir node’ni alohida to‘plamda (hash set) saqlashni talab qiladi:

FUNCTION HAS_CYCLE_WITH_SET(head)
    visited = BO'SH TO'PLAM
    current = head

    WHILE current != NULL
        IF current TO'PLAMDA MAVJUD
            RETURN TO'G'RI

        TO'PLAMGA current NI QO'SHISH
        current = current.next

    RETURN NOTO'G'RI

Bu yechim O(n) vaqt talab qiladi, ammo n ta node’ga reference saqlash uchun O(n) qo‘shimcha xotira ham kerak bo‘ladi. Node’larning o‘zini o‘zgartirmasdan va qo‘shimcha xotirasiz aniqlash mumkinmi degan savol boshqa yechimga olib keladi.

Optimal yechim: Floyd’ning tez va sekin ko‘rsatkich algoritmi

G‘oya o‘rtasini topish masalasidagi bilan bir xil ikkita reference’dan boshlanadi: slow har qadamda bitta node, fast esa har qadamda ikkita node oldinga siljiydi. Agar ro‘yxatda tsikl bo‘lmasa, fast oddiy ravishda oxiriga (NULLga) yetib, sikl to‘xtaydi. Agar tsikl mavjud bo‘lsa, fast tsikl ichida aylanib yurishda davom etadi va, muhimi, ma’lum vaqtdan keyin slowni quvib yetadi — ular bir xil node’da uchrashadi.

FUNCTION HAS_CYCLE(head)
    IF head = NULL
        RETURN NOTO'G'RI

    slow = head
    fast = head

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

        IF slow = fast
            RETURN TO'G'RI

    RETURN NOTO'G'RI

Nega ular albatta uchrashadi?

Tsikl bo‘lmasa, fast slowdan tezroq oxiriga yetib, sikl fast = NULL yoki fast.next = NULL sharti bilan to‘xtaydi — hech qachon uchrashuv bo‘lmaydi.

Tsikl mavjud bo‘lsa, ikkala reference ham oxir-oqibat tsikl ichiga kirib qoladi. Tsikl ichida fast slowga nisbatan har qadamda bitta node yaqinlashadi (chunki u ikki qadam, slow esa bir qadam yuradi, tsikl esa davriy, ya’ni chekli uzunlikka ega). Bu xuddi doiraviy yo‘lda ikki yugurchi — biri ikki barobar tez — bir-biriga qanchalik uzoqda boshlamasin, oxir-oqibat albatta bir joyda to‘qnashishiga o‘xshaydi. Masofa har qadamda kamayib boraveradi va tsikl chekli uzunlikda bo‘lgani uchun, masofa nolga yetadi — bu esa ikkalasi bir xil node’da turgani degani.

Bosqichma-bosqich misol

Ro‘yxat: 1 → 2 → 3 → 4, bunda 4ning nexti qaytadan 2ga ulangan (tsikl uzunligi 3).

Boshlanish: slow = 1, fast = 1

1-qadam: slow = 2, fast = 3
2-qadam: slow = 3, fast = 2   (fast: 3 -> 4 -> 2, tsikl bo'ylab aylandi)
3-qadam: slow = 4, fast = 4   ← slow = fast, TSIKL TOPILDI

Uchrashuv nuqtasi doim tsiklning boshlanish node’i bilan bir xil bo‘lishi shart emas — algoritm faqat tsikl bor-yo‘qligini aniqlaydi. Tsiklning aynan qaysi node’dan boshlanishini topish alohida qo‘shimcha qadamlarni talab qiladi (matematik jihatdan, uchrashuv nuqtasidan va headdan bir vaqtda, bir qadam tezlikda yurgan ikkita reference tsiklning boshlanish node’ida uchrashadi), ammo bu — “tsikl bormi?” degan savoldan tashqariga chiqadigan alohida masala.

Vaqt va xotira murakkabligi

fast har doim slowdan tezroq harakatlanadi, shuning uchun tsikl mavjud bo‘lsa, uchrashuv tsikl uzunligidan oshmaydigan miqdordagi qadamda sodir bo‘ladi. Tsikl bo‘lmasa, fast ro‘yxat oxiriga n / 2 qadamda yetadi. Har ikkala holatda ham bajariladigan qadamlar soni node’lar soniga mutanosib, shuning uchun vaqt murakkabligi O(n).

Qo‘shimcha xotira — faqat ikkita reference, slow va fast. Hash to‘plamli yechimdan farqli o‘laroq, bu son ro‘yxat uzunligidan mustaqil, shuning uchun xotira murakkabligi O(1). Aynan shu xotira tejami Floyd algoritmini hash to‘plamli yechimdan afzal qiladi, garchi ikkalasining ham vaqt murakkabligi O(n) bo‘lsa-da.

Nozik holatlar

Bo‘sh ro‘yxat. head = NULL bo‘lsa, funksiya darhol “tsikl yo‘q” javobini qaytarishi kerak.
Bitta elementli ro‘yxat, tsiklsiz. fast.next NULL, sikl birinchi tekshiruvda to‘xtaydi.
Bitta elementli ro‘yxat, o‘z-o‘ziga ulangan. Node’ning nexti o‘zini ko‘rsatsa, bu ham tsikl hisoblanadi. Birinchi qadamdayoq slow va fast bir xil node’da uchrashadi.
Butun ro‘yxat tsikl bo‘lsa (ya’ni headning o‘zi ham tsikl ichida bo‘lsa), algoritm baribir to‘g‘ri ishlaydi — ikkala reference ham boshidanoq tsikl ichida harakatlanadi.

Keng tarqalgan xatolar

Sikl shartini noto‘g‘ri yozish. fast.next.nextga murojaat qilishdan oldin fast.next != NULL ekanini tekshirmaslik NULL.nextga murojaat qilish xatosiga olib keladi. Shart har doim ikki qadamdan oldin ham, keyin ham xavfsizlikni ta’minlashi kerak.

Reference’larni qiymat bo‘yicha solishtirish. slow = fast tekshiruvi node’larning o‘zini, ya’ni ular bir xil manzilni ko‘rsatishini solishtirishi kerak, node’lar ichidagi qiymatlarni emas. Agar ro‘yxatda takroriy qiymatlar bo‘lsa-yu, solishtirish faqat qiymat bo‘yicha bajarilsa, tsikl yo‘q bo‘lsa ham noto‘g‘ri “tsikl bor” degan xulosaga kelish mumkin.

Tsikl bor deb, uni uzishni unutib qo‘yish. Ba’zi vazifalarda tsiklni faqat aniqlash emas, uni yo‘q qilish ham so‘raladi. Bu holatda tsiklning boshlanish node’ini topib, undan oldingi node’ning nextini NULLga o‘rnatish kerak bo‘ladi — bu “tsikl bormi?” savolidan keyingi qadam.

Xulosa

Tsiklni aniqlash uchun qo‘shimcha xotira shart emas — ikkita reference’ning nisbiy tezligi yetarli. Agar tsikl bo‘lmasa, tezroq yuruvchi reference oddiygina oxiriga yetadi; agar tsikl bo‘lsa, u tsikl ichida aylanib, sekinroq reference’ni albatta quvib yetadi. Bu yondashuv — fast-slow pointer texnikasining yana bir qo‘llanilishi — o‘rtani topish masalasidagi bilan bir xil g‘oyaga, ammo boshqa savolga tayanadi: masofani emas, uchrashuv sodir bo‘lish-bo‘lmasligini kuzatish.