O‘rtasini topish

Navbatda turgan odamlar qatorini tasavvur qiling. Qator boshi va oxiri ko‘rinib turibdi, lekin qatorda nechta odam borligini bilmaysiz. “Qatorning aynan o‘rtasidagi odamni top” deyilsa, eng oddiy yo‘l — avval boshidan oxirigacha sanab chiqish, keyin sonni ikkiga bo‘lib, yana boshidan o‘sha o‘ringacha yurish. Bu ikki marta yurishni talab qiladi. Xuddi shu masala linked list uchun ham tug‘iladi, faqat bu yerda “necha kishi borligini” array kabi darhol bilib bo‘lmaydi — buni bilish uchun ham ro‘yxat bo‘ylab yurish kerak.

Masala sharti

Bosh (head) reference’i berilgan singly linked list mavjud. Ro‘yxatning o‘rta node’ini topish kerak. Element soni juft bo‘lsa, odatda ikkinchi yarmning birinchi node’i o‘rta hisoblanadi — bu shart, albatta, masala qo‘yilishiga qarab o‘zgarishi mumkin, shuning uchun bu maqolada shu qoidaga amal qilamiz.

Kirish:  1 → 2 → 3 → 4 → 5 → NULL
Chiqish: 3   (o'rtadagi node)

Kirish:  1 → 2 → 3 → 4 → NULL
Chiqish: 3   (juft sonli ro'yxatda ikkinchi yarmning boshi)

Ro‘yxat bo‘sh bo‘lsa, o‘rta node ham mavjud emas. Bitta elementli ro‘yxatda o‘rta — shu yagona node’ning o‘zi.

Sodda yechim: uzunlikni avval hisoblash

Eng to‘g‘ridan-to‘g‘ri yo‘l — avval butun ro‘yxatni bir marta aylanib, uzunlikni hisoblash, keyin boshidan length / 2 marta qadam bosib, o‘rtaga yetib borish:

FUNCTION FIND_MIDDLE_TWO_PASS(head)
    length = 0
    current = head

    WHILE current != NULL
        length = length + 1
        current = current.next

    current = head
    steps = length / 2       // butun songa bo'lish

    FOR i FROM 0 TO steps - 1
        current = current.next

    RETURN current

Bu yechim to‘g‘ri ishlaydi, ammo ro‘yxat bo‘ylab ikki marta yuradi: birinchi marta uzunlikni bilish uchun, ikkinchi marta o‘rtaga yetib borish uchun. Vaqt murakkabligi baribir O(n) bo‘lsa-da, amalda ikki barobar ko‘proq qadam bosiladi. Bundan tashqari, ba’zi vaziyatlarda ro‘yxat bo‘ylab faqat bir marta yurish imkoni bo‘ladi — masalan, ma’lumot oqim (stream) tarzida kelayotgan bo‘lsa. Shu sababli bitta o‘tishda ishlaydigan yechim qulayroq.

Optimal yechim: sekin va tez ko‘rsatkich

G‘oya oddiy: ikkita reference bir vaqtning o‘zida headdan yurishni boshlaydi. Biri — slow — har qadamda bitta node oldinga siljiydi. Ikkinchisi — fast — har qadamda ikkita node oldinga siljiydi. fast ro‘yxat oxiriga yetganda, slow aynan o‘rtada bo‘ladi — chunki u fastdan ikki marta sekin yurgan.

FUNCTION FIND_MIDDLE(head)
    IF head = NULL
        RETURN NULL

    slow = head
    fast = head

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

    RETURN slow

Nega bu ishlaydi?

fast har qadamda slowdan ikki barobar tez yuradi. Demak, fast ro‘yxat oxiriga yetganda, u slowga nisbatan ikki barobar ko‘proq masofa bosib o‘tgan bo‘ladi. Boshqacha aytganda, slow aynan fast bosib o‘tgan masofaning yarmida turadi — bu esa ro‘yxatning o‘rtasi degani.

Sikl sharti (fast.next != NULL AND fast.next.next != NULL) ikkita holatni tekshiradi: fastning o‘zi emas, fast.next va fast.next.nextning mavjudligi. Bu shart tanlovi juft va toq uzunlikdagi ro‘yxatlar uchun qaysi node o‘rta hisoblanishini belgilaydi.

Bosqichma-bosqich misol

Toq uzunlikdagi ro‘yxat: 1 → 2 → 3 → 4 → 5 → NULL.

Boshlanish:  slow = 1, fast = 1

1-qadam: slow = 2, fast = 3
2-qadam: slow = 3, fast = 5

fast.next = NULL  → sikl to'xtaydi

Natija: slow = 3   (to'g'ri, chunki 3 - o'rtadagi element)

Juft uzunlikdagi ro‘yxat: 1 → 2 → 3 → 4 → NULL.

Boshlanish:  slow = 1, fast = 1

1-qadam: slow = 2, fast = 3
          tekshiruv: fast.next = 4 (mavjud), fast.next.next = NULL → sikl to'xtaydi

Natija: slow = 2 emas — tekshiramiz qaytadan

Diqqat bilan qarasak: birinchi qadamdan keyin fast = 3. Sikl sharti yana tekshiriladi: fast.next (ya’ni 4) mavjud, lekin fast.next.next (4dan keyingisi) NULL. Demak sikl davom etadi, chunki shart AND bilan bog‘langan va ikkalasi ham NULL bo‘lmasligi kerak edi — bu yerda ikkinchisi NULL, shuning uchun sikl to‘xtaydi va natija slow = 2 bo‘lib qoladi.

Kirish:  1 → 2 → 3 → 4 → NULL
Natija:  slow = 2

Izoh: bu qoida bo'yicha juft ro'yxatda "birinchi yarmning oxirgi elementi" o'rta hisoblanadi.

Note

Agar juft uzunlikda ikkinchi yarmning birinchi elementi o‘rta hisoblanishi kerak bo‘lsa, sikl sharti fast != NULL AND fast.next != NULL ko‘rinishida yoziladi. Ikkala variant ham to‘g‘ri; farq shunda — masala qaysi node’ni “o‘rta” deb belgilashiga bog‘liq. Shu sababli masalani yechishdan oldin bu shartni aniqlashtirib olish kerak.

Vaqt va xotira murakkabligi

Ro‘yxat bo‘ylab faqat bitta o‘tish bajariladi, ammo bu o‘tishda ikkita reference harakatlanadi. fast har safar ikki qadam bosgani uchun, u oxiriga yetganda slow taxminan n / 2 marta siljigan bo‘ladi. Umumiy bajarilgan qadamlar soni nga mutanosib, shuning uchun vaqt murakkabligi O(n) — xuddi ikki o‘tishli yechim kabi, lekin amaliy jihatdan ikki barobar kamroq harakat bilan.

Qo‘shimcha xotira — faqat ikkita reference, slow va fast. Ro‘yxat uzunligidan qat’i nazar bu son o‘zgarmaydi, shuning uchun xotira murakkabligi O(1).

Nozik holatlar

• Bo‘sh ro‘yxat. head = NULL bo‘lsa, funksiya darhol NULL qaytarishi kerak. Aks holda fast.nextga murojaat qilishga urinish xatoga olib keladi.
• Bitta elementli ro‘yxat. fast.next allaqachon NULL, shuning uchun sikl birinchi tekshiruvdayoq to‘xtaydi va slow = head qaytadi — bu to‘g‘ri natija.
• Ikkita elementli ro‘yxat. fast.next mavjud, lekin fast.next.next NULL. Sikl bir marta ham bajarilmaydi, natija tanlangan qoidaga qarab birinchi yoki ikkinchi node bo‘ladi.
• Tsikl bor ro‘yxat. Agar ro‘yxatda halqa mavjud bo‘lsa (ya’ni oxirgi node yana avvalgi node’ga ulangan bo‘lsa), fast.next yoki fast.next.next hech qachon NULL bo‘lmaydi va sikl to‘xtamaydi. Bu funksiya faqat tsiklsiz ro‘yxat uchun mo‘ljallangan; tsiklni aniqlash alohida masaladir (qarang: Tsikl bormi?).

Keng tarqalgan xatolar

Faqat fast != NULL tekshirish. Agar sikl sharti fast.next.nextni tekshirmasdan faqat fast != NULL bo‘lsa, fast.nextga murojaat qilinganda fast allaqachon NULL bo‘lishi mumkin — bu NULL.nextga murojaat qilish xatosiga olib keladi. Shart har doim keyingi murojaat qilinadigan node’larning mavjudligini oldindan tekshirishi kerak.

Uzunlikni noto‘g‘ri hisoblash. Ikki o‘tishli yechimda length / 2ni butun songa bo‘lishda ortiqcha yoki kam qadam bosish oson xato. Fast-slow usuli bu hisob-kitobni butunlay chetlab o‘tadi, chunki u uzunlikni bilishga ehtiyoj sezmaydi.

Juft/toq holatni aniqlashtirmaslik. Yuqorida ko‘rsatilganidek, juft uzunlikdagi ro‘yxatda qaysi node “o‘rta” hisoblanishi shartga bog‘liq. Bu aniqlanmasa, to‘g‘ri algoritm ham noto‘g‘ri natija berayotgandek ko‘rinishi mumkin.

Xulosa

Sekin va tez ko‘rsatkich (fast-slow pointer yoki “toshbaqa va quyon”) usuli linked listning o‘ziga xos xususiyatidan — index bo‘yicha bevosita kirish yo‘qligidan — kelib chiqadigan cheklovni chetlab o‘tadi: uzunlikni oldindan bilish shart emas, chunki ikkita ko‘rsatkichning nisbiy tezligi o‘rtani o‘zi topib beradi. Bu g‘oya linked list bilan bog‘liq boshqa ko‘plab masalalarda, jumladan ro‘yxatda tsikl bor-yo‘qligini aniqlashda ham qayta ishlatiladi.