Tarkibga o'tish

Teskari qilish

Bir qatorga tizilgan odamlarni tasavvur qiling: hammasi orqasini o‘girib, yuzlarini qarama-qarshi tomonga burishi kerak. Buning uchun odamlarning o‘zini ko‘chirish shart emas — ular joyida turgan holda faqat kimga qarab turishlarini o‘zgartirish kifoya. Linked listni teskari qilish ham aynan shu mantiqqa asoslanadi: node’lar xotirada o‘z joyida qoladi, faqat ularning bir-biriga bog‘lanish yo‘nalishi o‘zgaradi.

Masala sharti

Bosh (head) reference’i berilgan singly linked list mavjud. Ro‘yxatni shunday o‘zgartirish kerakki, oxirgi element yangi bosh, birinchi element esa yangi oxir bo‘lsin — va butun ketma-ketlik teskari tartibda o‘qilsin.

Kirish:  1 → 2 → 3 → 4 → NULL
Chiqish: 4 → 3 → 2 → 1 → NULL

Bo‘sh ro‘yxatni yoki bitta elementli ro‘yxatni teskari qilish natijasi o‘zgarishsiz qoladi.

Nega array’dagidek oddiy emas?

Arrayni teskari qilish uchun ikki chetdagi elementlarni index orqali almashtirish yetarli, chunki istalgan indexga O(1) vaqtda kirish mumkin. Linked listda esa oxirgi elementga index orqali bevosita kirib bo‘lmaydi — unga yetish uchun boshidan boshlab yurish kerak. Bundan tashqari, elementlarning qiymatini joy-joyida almashtirish o‘rniga, bog‘lanishning o‘zini — next reference’ini — teskari yo‘naltirish kerak bo‘ladi.

Optimal yechim: uchta ko‘rsatkich bilan iterativ teskari aylantirish

G‘oya: ro‘yxat bo‘ylab bir marta yurib, har bir node’ning nextini oldingi node’ga yo‘naltiramiz. Buning uchun uchta reference kerak bo‘ladi:

  • previous — hozirgacha teskari aylantirilgan qismning boshi (dastlab NULL, chunki hali hech narsa teskari aylantirilmagan);
  • current — hozir ishlov berilayotgan node;
  • next_node — current.nextni o‘zgartirishdan oldin uni vaqtincha saqlab turadigan reference.
FUNCTION REVERSE(head)
    previous = NULL
    current = head

    WHILE current != NULL
        next_node = current.next   // eski bog'lanishni yo'qotmaslik uchun saqlab qo'yamiz
        current.next = previous    // bog'lanishni teskari yo'naltiramiz
        previous = current         // "teskari aylantirilgan qism" bir node oldinga siljiydi
        current = next_node        // asl ro'yxat bo'ylab bir node oldinga siljiymiz

    RETURN previous   // sikl tugaganda previous - yangi head

next_node reference’i shart, chunki current.next = previous bajarilgan zahoti currentdan asl ro‘yxatdagi keyingi node’ga olib boruvchi yagona yo‘l yo‘qoladi. Agar bu qadamdan oldin next_nodeda saqlab qo‘yilmasa, zanjirning qolgan qismi butunlay yo‘qoladi.

Bosqichma-bosqich misol

Kirish: 1 → 2 → 3 → NULL.

Boshlanish:
previous = NULL
current  = [1]
[1] → [2] → [3] → NULL


1-qadam (current = 1):
next_node = 2
1.next = previous (NULL)      →  NULL ← [1]    [2] → [3] → NULL
previous = 1
current = 2


2-qadam (current = 2):
next_node = 3
2.next = previous (1)         →  NULL ← [1] ← [2]    [3] → NULL
previous = 2
current = 3


3-qadam (current = 3):
next_node = NULL
3.next = previous (2)         →  NULL ← [1] ← [2] ← [3]
previous = 3
current = NULL   → sikl to'xtaydi


Natija: previous = [3], demak yangi head = 3

Yakuniy ko'rinish:  3 → 2 → 1 → NULL

Har bir qadamda faqat bitta next reference’i o‘zgaradi. Qiymatlarning o‘zi — 1, 2, 3 — hech qayerga ko‘chirilmadi; ular xotirada o‘z joyida qoldi, o‘zgargani faqat ular orasidagi yo‘nalish.

Nega bu ishlaydi?

Sikl invarianti quyidagicha ta’riflanadi: har bir iteratsiya boshlanishida previous orqali erishiladigan zanjir — asl ro‘yxatning currentgacha bo‘lgan qismining teskari holatidir. Boshida bu zanjir bo‘sh (previous = NULL), chunki hali hech narsa teskari aylantirilmagan. Har qadamda bitta node shu teskari zanjirga qo‘shiladi, va current asl ro‘yxat bo‘ylab bir qadam oldinga siljiydi. current NULLga yetganda, butun ro‘yxat teskari zanjirga qo‘shilgan bo‘ladi — shu sababli previous yangi head bo‘ladi.

Vaqt va xotira murakkabligi

Har bir node aynan bir marta ko‘riladi va unda doimiy miqdordagi amal (uchta reference yangilanishi) bajariladi. Shu sababli vaqt murakkabligi O(n). Yordamchi xotira sifatida faqat uchta reference — previous, current, next_node — ishlatiladi, ro‘yxat uzunligidan qat’i nazar bu son o‘zgarmaydi, shuning uchun xotira murakkabligi O(1).

Rekursiv variant

Xuddi shu masalani rekursiv usulda ham yechish mumkin:

FUNCTION REVERSE_RECURSIVE(current, previous)
    IF current = NULL
        RETURN previous

    next_node = current.next
    current.next = previous
    RETURN REVERSE_RECURSIVE(next_node, current)

Vaqt murakkabligi baribir O(n), chunki har bir node uchun bitta chaqiruv bajariladi. Ammo bu yerda qo‘shimcha xotira O(1) emas, O(n), chunki har bir rekursiv chaqiruv call stackda joy egallaydi. Juda uzun ro‘yxatda bu stack chegarasidan oshib ketishi mumkin. Shu sababli amaliyotda iterativ variant odatda afzal ko‘riladi.

Nozik holatlar

  • Bo‘sh ro‘yxat. head = NULL bo‘lsa, sikl birinchi tekshiruvdayoq to‘xtaydi va funksiya NULL qaytaradi — bu to‘g‘ri natija.
  • Bitta elementli ro‘yxat. Sikl bir marta bajariladi: current.next previousga, ya’ni NULLga o‘rnatiladi. Natija — o‘zgarishsiz qolgan bitta node.
  • Doubly linked listni teskari qilish. Bu holatda har bir node’da next va previous ham joy almashishi kerak, bundan tashqari ro‘yxatning head va tail boshqaruv reference’lari ham almashtiriladi. Bu maqoladagi singly linked list uchun yozilgan algoritm to‘g‘ridan-to‘g‘ri qo‘llanmaydi, ammo asosiy g‘oya — bog‘lanish yo‘nalishini teskari aylantirish — bir xil qoladi.

Keng tarqalgan xatolar

next_nodeni saqlamaslik. Bu eng ko‘p uchraydigan xato. current.next = previous bajarilishidan oldin current.nextning asl qiymati boshqa joyda saqlanmasa, undan keyingi butun zanjirga yo‘l uziladi va faqat bitta node qaytariladi.

Yangi head’ni noto‘g‘ri qaytarish. Sikl tugagach current doim NULL bo‘ladi — yangi head emas. Yangi head har doim previousda saqlanadi, chunki aynan u охирги ishlov berilgan node’ni ko‘rsatib turadi.

Asl headni yo‘qotib qo‘yish. Agar chaqiruvchi kod funksiyadan qaytgan qiymatni saqlamasa yoki eski head reference’iga tayanishda davom etsa, teskari aylantirilgan ro‘yxatning boshiga endi faqat bitta reference — funksiyadan qaytgan qiymat — orqali yetish mumkinligini unutib qo‘yishi mumkin. Eski head endi ro‘yxatning oxirgi elementiga aylanadi, boshiga emas.

Xulosa

Linked listni teskari qilish qiymatlarni ko‘chirishni emas, faqat bog‘lanishlar yo‘nalishini o‘zgartirishni talab qiladi. Uchta reference — previous, current, next_node — yordamida ro‘yxat bo‘ylab bir marta yurib, har bir next bog‘lanishini teskari yo‘naltirish bu masalaning markazidagi g‘oya. Xuddi shu “bog‘lanishni almashtirishdan oldin eskisini saqlab qo‘yish” tamoyili linked list bilan ishlashning ko‘plab boshqa masalalarida, jumladan ikki ro‘yxatni birlashtirishda ham qayta uchraydi.