Qo'yilgan masala

Misollar:

1. Bog’lamli ro'yxatni teskari aylantiring.

Bog’lamli ro'yxatni joyiga aylantirish uchun funktsiya yarating. Siz asl ro'yxatning sarlavhasidan foydalanasiz va teskari ro'yxatning sarlavhasini qaytarasiz.
Bu muammoning hiylasi shundaki, teskari o'zgarish doimiy fazoda sodir bo'lishi kerak. Shuning uchun biz yangi ro'yxat yaratmaymiz va proksi-server qo'shmaymiz yoki foydalanmaymiz. Bu to'g'ridan-to'g'ri ushbu ro'yxat bilan ishlash orqali amalga oshirilishi kerak.
def reversal(head):
current = head #
prev = None
next_node = None
while current:
next_node = current.nextnode
current.nextnode = prev
prev = current
current = nextnode
return prev
Yuqoridagi kodda tushuntirilganidek, biz har bir tugun uchun ko'rsatgichlarni almashtiramiz. Kirish - bog’lamli ro'yxatning joriy bobi - yoki bizning misollarimizda. Keyin funktsiya har bir tugun bo'ylab yuradi va keyingi tugun atributining yo'nalishini o'zgartiradi. Qo'shimcha vizualizatsiya uchun quyidagi rasmga qarang.

Ushbu yondashuv xotira xarajatlarini kamaytirish va intervyu oluvchilarni yangi ro'yxat yaratmasdan va jarayonni O (n) vaqt davomida ushlab turmasdan ishlash qobiliyati bilan hayratda qoldirish afzalligiga ega.

2. N-dan oxirgi tugungacha bog’langan ro'yxat hosil qiling?

Bosh tugun va n butun sonini oladigan va keyin ro'yxatdagi n-chi va oxirgi tugunni qaytaradigan funksiya yarating.
Ushbu vazifaning hiylasi ro'yxatni ikkita o'q bilan aylanib o'tishdir. Birinchi marker takrorlanadi va oxirgidan oldingi tugun haqiqatda mavjudligini tekshiradi. Ikkinchi marker orqaga o'tadi va shu tugunda tugaydi.
def nth_last_node(n,head):
pointer_1 = head
pointer_2 = head
for i in range(n-1):
if not pointer_1.nextnode:
raise LookupError('Error: Command continues past index of list')
pointer_1 = pointer_1.nextnode
while pointer_1.nextnode:
pointer_2 = pointer_2.nextnode
pointer_1 = pointer_1.nextnode
return pointer_2
Kod ular orasida bo'sh joy yaratishda ajoyib ish qilsa-da, keling, ingl.

Birinchi va ikkinchi bosqichlar orasida ko'rib turganingizdek, g'oya shundan iboratki, 1-ko'rsatgich o'zi va 2-ko'rsatkich o'rtasida n ta tugun masofasini yaratishi kerak. Xavfsiz bo'lgandan so'ng, ikkita ko'rsatgich birgalikda harakatlanishi mumkin - 1-ko'rsatgich ro'yxat tugagan yoki yo'qligini tekshiradi va 2-ko'rsatgich o'zining joriy holatini n-chi tugungacha e'lon qilishga tayyor.
Hammasi shu. Bizda bog’lamli ro'yxat nima ekanligi va u haqida qanday savollar berish kerakligi haqida asosiy asoslar bor edi.