Linked list masalalari: ag'darish, tez va sekin ko'rsatkich, dummy head

Qisqacha: Linked list masalalarining butun siri — havolalarni to'g'ri tartibda qayta ulash. Ag'darishda uchta ko'rsatkich (prev, current, next) har strelkani orqaga buradi — O(n) vaqt, O(1) xotira. Tez va sekin ko'rsatkich (biri 2 qadam, biri 1 qadam) ro'yxat o'rtasini topadi va siklni aniqlaydi (Floyd). Dummy head — soxta bosh tugun — "ro'yxat bo'shmi, head o'zgaradimi?" degan maxsus holatlarni yo'qotadi. Doubly list orqaga havola qo'shib, ma'lum tugunni O(1) da o'chiradi; circular list esa doira bo'lib aylanadi.

Bu darsda

• Ro'yxatni qo'shimcha xotirasiz ag'dara olasiz va havolalarni qaysi tartibda o'zgartirish kerakligini tushuntira olasiz.
• Tez va sekin ko'rsatkich bilan o'rtani topasiz va siklni Floyd algoritmi bilan aniqlaysiz.
• Dummy head bilan ikki saralangan ro'yxatni birlashtirasiz va oxiridan n-tugunni o'chirasiz.
• Doubly va circular list qachon kerakligini va ularning tuzoqlarini bilasiz.

Oldin bilishingiz kerak: Linked list: tuzilishi va asosiy amallar, Ikki ko'rsatkich, reduce.

1. Nega bu kerak?

Oldingi darsda Sardor oshxona navbatini linked list'ga o'tkazdi. Endi Jasur aka yangi talablar qo'ydi:

1. Ekranda buyurtmalar tarixi teskari tartibda chiqsin — eng yangisi tepada.
2. Navbat juda uzun bo'lsa, uning ikkinchi yarmi ikkinchi oshpazga berilsin. O'rtani bir o'tishda topish kerak.
3. Bir kuni ekran qotib qoldi. Ma'lum bo'ldiki, xato tufayli oxirgi tugun o'rtadagi tugunga ulanib qolgan — zanjir doiraga aylangan. Bunday xatoni avtomatik aniqlash kerak.
4. Ikki filial (Chilonzor va Yunusobod) buyurtmalari vaqt bo'yicha tartiblangan. Ularni bitta tartiblangan ro'yxatga birlashtirish kerak.

To'rttala masala ham havolalar bilan ishlash. Har birida qo'shimcha massivga ko'chirib, hammasini oson qilish mumkin — lekin bu O(n) xotira. Bugun ularni joyida, havolalarni to'g'ri qayta ulab yechamiz. Bu masalalar intervyularda eng ko'p beriladigan savollar orasida.

2. Ishchi asboblar

Oldingi darsda tugunni ListNode klassi bilan yasagan edik. Bu darsda uni qisqaroq yozamiz: node(value, next) funksiyasi new ListNode(value, next) bilan bir xil shakldagi obyekt qaytaradi — value va next maydonlari bor. Masalalar kodi ikkalasi bilan ham bir xil ishlaydi, faqat har blok qisqaroq bo'ladi. Ikki yordamchi ham qo'shamiz: massivdan ro'yxat yasash va ro'yxatni massivga aylantirish (konsolda ko'rish uchun):

const node = (value, next = null) => ({ value, next });
const fromArray = (values) =>
  values.reduceRight((next, value) => node(value, next), null);
function toArray(head) {
  const out = [];
  for (let c = head; c !== null; c = c.next) out.push(c.value);
  return out;
}

const head = fromArray([101, 102, 103]);
console.log(head.value, head.next.value); // 101 102
console.log(toArray(head)); // [ 101, 102, 103 ]

reduceRight massivni o'ngdan aylanadi (reduce ning teskarisi). Oxirgi elementdan boshlab, har birini oldingi natijaning oldiga qo'yadi: avval 103 → null, keyin 102 → 103, keyin 101 → 102. Quyidagi har kod blokida shu uch qator takrorlanadi — har blok alohida ishlashi uchun.

3. Ro'yxatni ag'darish

3.1 Sodda yechim

Eng birinchi yo'l: qiymatlarni massivga yig'ib, teskari tartibda yangi ro'yxat qurish. Ishlaydi, lekin O(n) qo'shimcha xotira — n ta qiymat va n ta yangi tugun. Linked list'ning o'zi esa joyida ag'darilishi mumkin: tugunlar joyida qoladi, faqat strelkalar buriladi.

3.2 G'oya: har strelkani orqaga burish

Har tugunda next strelkasi o'ngga qaragan. Ag'darish — har strelkani chapga burish. Lekin ehtiyot bo'ling: current.next ni o'zgartirgan zahoti undan keyingi zanjirga yo'l yo'qoladi. Shuning uchun avval keyingisini saqlab qo'yamiz, keyin buramiz. Uchta ko'rsatkich kerak: prev (allaqachon ag'darilgan qism boshi), current (hozirgi tugun) va next (hali ag'darilmagan qism boshi).

3.3 Yechim va murakkablik

const node = (value, next = null) => ({ value, next });
const fromArray = (values) =>
  values.reduceRight((next, value) => node(value, next), null);
function toArray(head) {
  const out = [];
  for (let c = head; c !== null; c = c.next) out.push(c.value);
  return out;
}

function reverse(head) {
  let prev = null;
  let current = head;
  while (current !== null) {
    const next = current.next; // 1. saqlash
    current.next = prev; // 2. burish
    prev = current; // 3. surish
    current = next;
  }
  return prev;
}

console.log(toArray(reverse(fromArray([101, 102, 103, 104]))));
console.log(reverse(null)); // null

Konsolda:

[ 104, 103, 102, 101 ]
null

Har tugun bir marta — O(n) vaqt. Uchta ko'rsatkich — O(1) xotira. Bo'sh ro'yxatda sikl aylanmaydi, prev — null qaytadi. Uch qadam tartibini eslab qoling: saqla, bur, sur.

Endi o'zingiz kuzating. Ro'yxat 101 → 102 → 103. Ikkinchi aylanishdan keyin (102 ham burilgach) prev qaysi tugunda turadi? Javob: .

Tekshirib ko'ring: Rekursiv ag'darish ham bor: "qolganini ag'dar, keyin o'zingni oxiriga ula". Uning xotirasi qancha?

4. Tez va sekin ko'rsatkich

4.1 O'rtasini topish

Navbat o'rtasini qanday topamiz? Sodda yo'l — ikki o'tish: avval uzunlikni sanaymiz, keyin yarmigacha yuramiz. Bitta o'tishda ham bo'ladi: ikkita ko'rsatkichni head'dan chiqaramiz. Sekin (slow) har safar bitta, tez (fast) ikkita qadam tashlaydi. Tez oxiriga yetganda, sekin aynan yarim yo'lda bo'ladi — xuddi bir xil vaqtda yugurgan ikki kishidan biri ikki baravar tez bo'lsa.

const node = (value, next = null) => ({ value, next });
const fromArray = (values) =>
  values.reduceRight((next, value) => node(value, next), null);

function middle(head) {
  let slow = head;
  let fast = head;
  while (fast !== null && fast.next !== null) {
    slow = slow.next; // 1 qadam
    fast = fast.next.next; // 2 qadam
  }
  return slow;
}

const odd = fromArray([101, 102, 103, 104, 105]);
const even = fromArray([101, 102, 103, 104]);
console.log(middle(odd).value); // 103
console.log(middle(even).value); // 103

Toq uzunlikda — aniq o'rta. Juft uzunlikda ikkita "o'rta" bor (102 va 103) — bu kod ikkinchisini qaytaradi. Birinchisi kerak bo'lsa, shartni fast.next !== null && fast.next.next !== null qiling. Shart tartibi muhim: avval fast !== null, keyin fast.next. Teskarisi null ning xususiyatini o'qishga urinadi.

Ikki ko'rsatkich darsida bir yo'nalishli tez/sekin ko'rsatkichni massivda ko'rgan edik. Bu yerda u yana ham foydali: ro'yxatda indeks yo'q, length ham yo'q.

4.2 Sikl aniqlash: Floyd algoritmi

Endi qotib qolgan ekran. Ro'yxatda sikl (cycle) bor: qaysidir tugunning next i oldingi tugunlardan biriga qaytadi. Bu — Ikki ko'rsatkich darsidagi manzillar "aylanasi"ning o'zi. while (current !== null) hech qachon tugamaydi.

Diqqat: Bu darsda "sikl" so'zi ikki ma'noda keladi. Ro'yxatdagi sikl — zanjirdagi halqa (cycle): strelkalar bo'ylab yurib, avval ko'rgan tugunga qaytasiz. Kodning while sikli (loop) esa — takrorlanadigan buyruqlar. Halqali ro'yxatda while sikli tugamaydi — muammo aynan shu.

Sodda yechim — ko'rilgan tugunlarni Set ga yig'ish: bir tugun ikkinchi marta uchrasa — sikl. O(n) vaqt, lekin O(n) xotira. Floyd usulini ("toshbaqa va quyon") Ikki ko'rsatkich darsida manzillar ustida ko'rgan edik. Endi uni ro'yxatda qo'llaymiz: xuddi o'rtani topishdagi ikki ko'rsatkich ishlaydi. Sikl yo'q bo'lsa — tez ko'rsatkich null ga yetadi. Sikl bo'lsa — ikkalasi sikl ichiga kirib, aylanaveradi. Tez sekindan har qadamda bitta tugun yaqinlashadi, shuning uchun albatta uni quvib yetadi:

Ikkinchi bosqich siklning boshini topadi — qaysi strelka xato qo'yilganini bilish uchun kerak. Nega ishlaydi? Uchrashgan paytda fast ikki baravar ko'p yo'l bosgan. Hisoblasak, head dan sikl boshigacha masofa uchrashuv joyidan sikl boshigacha (aylana bo'ylab) masofaga teng chiqadi. Shuning uchun bittadan yurgan ikki ko'rsatkich aynan sikl boshida uchrashadi. Isbotni bilish shart emas, lekin intervyuda so'rashadi.

4.3 O'lchov: Floyd va Set

n ta tugunli ro'yxatni (oxiri o'rtaga ulangan) ikki usulda tekshirdik. Usul — benchmarking darsidagidek: har n alohida jarayonda, isitish, mediana:

Floyd medianalari sakrab turdi (2 mln da goh 6, goh 12 ms) — tugunlar xotirada qanday joylashganiga bog'liq. Shuning uchun eng tez natijani ham qo'ydik: unda n ikki baravar — vaqt aniq ikki baravar. Ikkalasi O(n), lekin Set taxminan 25 baravar sekin: har tugunni xesh jadvalga yozish millionlab qo'shimcha ish va xotira talab qiladi.

Tekshirib ko'ring: Floyd'da tez ko'rsatkich 2 emas, 3 qadam tashlasa, sikl baribir aniqlanadimi?

5. Dummy head: soxta bosh

5.1 Ikki saralangan ro'yxatni birlashtirish

Chilonzor buyurtmalari: 10:10, 10:45, 11:00. Yunusobod: 10:20, 10:30, 12:00. Ikkalasi ham vaqt bo'yicha tartiblangan. Bitta tartiblangan ro'yxat kerak.

G'oya: ikki ro'yxat boshlarini solishtiramiz, kichigini natijaga ulaymiz va o'sha ro'yxatda bir qadam suramiz. Muammo — natijaning birinchi tugunini qanday boshlash? "Natija hali bo'shmi?" degan tekshiruv har qadamda halaqit beradi. Yechim — dummy head (soxta bosh): ma'nosiz qiymatli bitta tugun yaratamiz va natijani uning orqasidan quramiz. Oxirida dummy.next ni qaytaramiz:

const node = (value, next = null) => ({ value, next });
const fromArray = (values) =>
  values.reduceRight((next, value) => node(value, next), null);
function toArray(head) {
  const out = [];
  for (let c = head; c !== null; c = c.next) out.push(c.value);
  return out;
}

function mergeSorted(a, b) {
  const dummy = node(0); // soxta bosh — qiymati ahamiyatsiz
  let tail = dummy; // natijaning oxiri
  while (a !== null && b !== null) {
    if (a.value <= b.value) {
      tail.next = a;
      a = a.next;
    } else {
      tail.next = b;
      b = b.next;
    }
    tail = tail.next;
  }
  tail.next = a ?? b; // qolgan qismni butunligicha ulaymiz
  return dummy.next;
}

const chilonzor = fromArray([1010, 1045, 1100]);
const yunusobod = fromArray([1020, 1030, 1200]);
console.log(toArray(mergeSorted(chilonzor, yunusobod)));

Konsolda:

[ 1010, 1020, 1030, 1045, 1100, 1200 ]

Vaqtlar soat va daqiqani qo'shib yozilgan son: 1045 — 10:45. Yangi tugun yaratilmadi — mavjudlari qayta ulandi. Vaqt O(n + m) (ikki ro'yxat uzunliklari yig'indisi), xotira O(1). tail.next = a ?? b — bitta ro'yxat tugagach, ikkinchisining qolgan qismi allaqachon tartiblangan, uni butunligicha ulash yetarli. <= tufayli teng vaqtlarda Chilonzor buyurtmasi oldin turadi — tartib barqaror.

5.2 Dummy nega yordam beradi

Dummy'siz kodda natija head'ini alohida tanlash kerak bo'lardi: if (head === null) head = … else tail.next = …. Ro'yxat boshini o'zgartiradigan har amalda (birinchi tugunni o'chirish, boshiga qo'yish) shunday if lar ko'payadi. Dummy bilan "birinchi tugun" ham oddiy tugun kabi, kimningdir next i bo'lib qoladi. Bitta qo'shimcha obyekt — O(1) xotira — evaziga kod qisqaradi va xatolar kamayadi. 2-mashqda dummy yana kerak bo'ladi.

6. Doubly va circular list

6.1 Doubly linked list: ikki tomonga havola

Oldingi darsda o'chirishning asosiy muammosi — oldingi tugunni topish edi (O(n)). Doubly linked list (ikki tomonlama bog'langan ro'yxat) da har tugunda ikkita havola bor: next va prev. Tugun qo'lingizda bo'lsa, uni O(1) da o'chirasiz — qo'shnilari o'sha zahoti ma'lum.

«Bahor»da mijoz buyurtmani bekor qilsa, uni navbatdan qidirmasdan olib tashlash kerak. Har buyurtma tugunini Map da id bo'yicha saqlaymiz:

class DNode {
  constructor(value) {
    this.value = value;
    this.prev = null;
    this.next = null;
  }
}

class DoublyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
  }
  append(value) {
    const node = new DNode(value);
    if (this.tail === null) {
      this.head = this.tail = node;
    } else {
      node.prev = this.tail;
      this.tail.next = node;
      this.tail = node;
    }
    return node; // tugunni qaytaramiz — keyin O(1) o'chirish uchun
  }
  remove(node) {
    if (node.prev) node.prev.next = node.next;
    else this.head = node.next; // head edi
    if (node.next) node.next.prev = node.prev;
    else this.tail = node.prev; // tail edi
    node.prev = node.next = null;
  }
  *[Symbol.iterator]() {
    for (let c = this.head; c !== null; c = c.next) yield c.value;
  }
}

const kitchen = new DoublyLinkedList();
const byId = new Map();
for (const id of [101, 102, 103, 104]) {
  byId.set(id, kitchen.append(id));
}
kitchen.remove(byId.get(103)); // mijoz bekor qildi — qidirmasdan
kitchen.remove(byId.get(101)); // head ham bekor
console.log([...kitchen]); // [ 102, 104 ]
console.log(kitchen.tail.prev.value); // 102

remove da to'rtta holat bor: tugun o'rtada, boshida, oxirida yoki yagona. if (node.prev) va if (node.next) ularning hammasini qamraydi. Narxi: har tugunda bitta qo'shimcha havola (ko'proq xotira) va har amalda ikki baravar ko'p havolani to'g'ri yangilash. Map + doubly list juftligi — LRU kesh ning asosi.

6.2 Circular list: doira

Circular linked list (halqasimon ro'yxat) da oxirgi tugun null ga emas, head ga ishora qiladi. Aylana bo'ylab cheksiz yurish mumkin — navbatma-navbat ishlar uchun qulay. «Bahor»ning uch kuryeri buyurtmalarni navbat bilan oladi:

const node = (value, next = null) => ({ value, next });
const ali = node("Ali");
const vali = node("Vali");
const hasan = node("Hasan");
ali.next = vali;
vali.next = hasan;
hasan.next = ali; // oxiri boshiga ulanadi — doira

let courier = ali;
for (const order of [101, 102, 103, 104, 105]) {
  console.log(order, "→", courier.value);
  courier = courier.next; // navbatdagi kuryer
}

Konsolda:

101 → Ali
102 → Vali
103 → Hasan
104 → Ali
105 → Vali

Bu usul round-robin ("navbat bilan aylanish") deyiladi: operatsion tizim protsessor vaqtini dasturlarga, yuk taqsimlagich so'rovlarni serverlarga shunday bo'ladi. Ehtiyot bo'ling: circular list'da while (c !== null) hech qachon tugamaydi — aylanishni "boshlang'ich tugunga qaytdikmi?" sharti bilan to'xtatish kerak. Floyd usuli esa aynan shunday ro'yxatni "xato" deb topadi — doira ataylab qilinganmi yoki tasodifiy, buni kod bilmaydi.

7. Chegaraviy holatlar

Birlashtirishda: ikkalasi bo'sh — null; biri bo'sh — ikkinchisi butunligicha; teng qiymatlar — birinchi ro'yxatdagisi oldin (<= tufayli).

O'ziga ulangan tugun (a.next = a) — eng kichik sikl. Ag'darish va o'rtani topish sikli ro'yxatda abadiy aylanadi. Ishonchsiz ma'lumotda avval hasCycle bilan tekshiring.

8. Ko'p uchraydigan xatolar

8.1 next ni saqlamasdan burish

current.next = prev; // ❌ keyingi zanjirga yo'l yo'qoldi
current = current.next; // endi bu prev — orqaga ketdik

Sikl bir qadamdan keyin to'xtaydi, ro'yxatning qolgan qismi yo'qoladi. Tuzatish: saqla → bur → sur: const next = current.next birinchi.

8.2 fast.next.next da null

while (fast.next !== null) — fast ning o'zi null bo'lsa, TypeError: Cannot read properties of null (reading 'next'). Tuzatish: fast !== null && fast.next !== null — && qisqa tutashuvi tufayli ikkinchi qism faqat birinchisi rost bo'lsa tekshiriladi.

8.3 dummy ni qaytarish

return dummy — natija boshida ortiqcha 0 paydo bo'ladi. Tuzatish: return dummy.next.

8.4 Doubly list'da prev ni unutish

next lar to'g'ri, prev lar eski — oldinga yurish ishlaydi, orqaga yurish buzilgan tugunlarga olib boradi. Tuzatish: har o'zgarishda ikkala yo'nalishni tekshiring; testda tail.prev ni ham sinang.

9. Mashqlar

1-mashq (oson): Qog'ozda

(a) 1 → 2 → 3 → null ni ag'darishda har aylanishdan keyin prev va current qaysi tugunda? (b) 1 → 2 → 3 → 4 → 2 (4 dan keyin yana 2) ro'yxatida Floyd'ning birinchi bosqichida slow va fast qayerda uchrashadi?

2-mashq (o'rta): Oxiridan n-chisini o'chirish

Navbat oxiridan n-buyurtmani bitta o'tishda o'chiring: removeNthFromEnd(head, n). Masalan, 101 → 102 → 103 → 104 → 105 dan n = 2 — 104 o'chadi. Ishora: ikki ko'rsatkichni orasida n qadam masofa bilan yuring — oldingisi oxiriga yetganda, orqadagisi o'chiriladigan tugundan oldin turadi. Head o'chishi mumkin (n = uzunlik) — dummy ishlating.

const node = (value, next = null) => ({ value, next });
const fromArray = (values) =>
  values.reduceRight((next, value) => node(value, next), null);
function toArray(head) {
  const out = [];
  for (let c = head; c !== null; c = c.next) out.push(c.value);
  return out;
}

function removeNthFromEnd(head, n) {
  const dummy = node(0, head);
  let fast = dummy;
  let slow = dummy;
  for (let i = 0; i < n; i++) fast = fast.next; // n qadam oldinda
  while (fast.next !== null) {
    fast = fast.next;
    slow = slow.next;
  }
  slow.next = slow.next.next; // slow — o'chiriladigandan oldingi
  return dummy.next;
}

const queue = () => fromArray([101, 102, 103, 104, 105]);
console.log(toArray(removeNthFromEnd(queue(), 2)));
console.log(toArray(removeNthFromEnd(queue(), 5)));

[ 101, 102, 103, 105 ]
[ 102, 103, 104, 105 ]

3-mashq (qiyin): Masalalar to'plami va testlar

kurs/mashqlar/14/17-royxat-masalalari/masalalar.test.mjs faylida beshta funksiya yozing: reverse, middle, hasCycle, mergeSorted, removeNthFromEnd. node:test bilan har birini "Chegaraviy holatlar" jadvali bo'yicha sinang: bo'sh ro'yxat, bitta tugun, juft uzunlik, o'ziga ulangan tugun, head'ni o'chirish.

// kurs/mashqlar/14/17-royxat-masalalari/masalalar.test.mjs
import { test } from "node:test";
import assert from "node:assert/strict";

const node = (value, next = null) => ({ value, next });
const fromArray = (values) =>
  values.reduceRight((next, value) => node(value, next), null);
function toArray(head) {
  const out = [];
  for (let c = head; c !== null; c = c.next) out.push(c.value);
  return out;
}

function reverse(head) {
  let prev = null;
  let current = head;
  while (current !== null) {
    const next = current.next;
    current.next = prev;
    prev = current;
    current = next;
  }
  return prev;
}

function middle(head) {
  let slow = head;
  let fast = head;
  while (fast !== null && fast.next !== null) {
    slow = slow.next;
    fast = fast.next.next;
  }
  return slow; // juft uzunlikda — ikkinchi o'rtasi
}

function hasCycle(head) {
  let slow = head;
  let fast = head;
  while (fast !== null && fast.next !== null) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) return true;
  }
  return false;
}

function mergeSorted(a, b) {
  const dummy = node(0);
  let tail = dummy;
  while (a !== null && b !== null) {
    if (a.value <= b.value) {
      tail.next = a;
      a = a.next;
    } else {
      tail.next = b;
      b = b.next;
    }
    tail = tail.next;
  }
  tail.next = a ?? b;
  return dummy.next;
}

function removeNthFromEnd(head, n) {
  const dummy = node(0, head);
  let fast = dummy;
  let slow = dummy;
  for (let i = 0; i < n; i++) fast = fast.next; // n qadam oldinda
  while (fast.next !== null) {
    fast = fast.next;
    slow = slow.next;
  }
  slow.next = slow.next.next;
  return dummy.next;
}

test("ag'darish", () => {
  assert.deepEqual(toArray(reverse(fromArray([1, 2, 3]))), [3, 2, 1]);
  assert.equal(reverse(null), null);
  assert.deepEqual(toArray(reverse(fromArray([7]))), [7]);
});

test("o'rtasi", () => {
  assert.equal(middle(fromArray([1, 2, 3, 4, 5])).value, 3);
  assert.equal(middle(fromArray([1, 2, 3, 4])).value, 3);
  assert.equal(middle(null), null);
});

test("sikl", () => {
  const head = fromArray([1, 2, 3, 4]);
  assert.equal(hasCycle(head), false);
  head.next.next.next.next = head.next; // 4 → 2
  assert.equal(hasCycle(head), true);
  const self = node(1);
  self.next = self; // o'ziga
  assert.equal(hasCycle(self), true);
});

test("ikki saralangan ro'yxatni birlashtirish", () => {
  const a = fromArray([1010, 1045, 1100]);
  const b = fromArray([1020, 1030, 1200]);
  assert.deepEqual(toArray(mergeSorted(a, b)),
    [1010, 1020, 1030, 1045, 1100, 1200]);
  assert.deepEqual(toArray(mergeSorted(null, fromArray([5]))), [5]);
});

test("oxiridan n-chisini o'chirish", () => {
  const list = () => fromArray([101, 102, 103, 104, 105]);
  assert.deepEqual(toArray(removeNthFromEnd(list(), 2)),
    [101, 102, 103, 105]);
  assert.deepEqual(toArray(removeNthFromEnd(list(), 5)),
    [102, 103, 104, 105]); // head o'chdi — dummy yordam berdi
  assert.deepEqual(toArray(removeNthFromEnd(fromArray([1]), 1)), []);
});

✔ ag'darish (1.3747ms)
✔ o'rtasi (0.1593ms)
✔ sikl (0.1228ms)
✔ ikki saralangan ro'yxatni birlashtirish (1.2737ms)
✔ oxiridan n-chisini o'chirish (0.261ms)
ℹ tests 5
ℹ suites 0
ℹ pass 5
ℹ fail 0
ℹ cancelled 0
ℹ skipped 0
ℹ todo 0
ℹ duration_ms 93.0987

4-mashq: Amaliy tajriba — murakkablik jadvali

kurs/mashqlar/14/MURAKKABLIK.md dagi algoritmlar jadvaliga shu darsning beshta masalasini qo'shing (sodda va yaxshi yechim bilan). "Ma'lumotlar tuzilmalari" jadvaliga esa doubly list ustunini qo'shing.

| Masala | Yechim | Vaqt | Xotira |
|---|---|---|---|
| Ro'yxatni ag'darish | massiv orqali | O(n) | O(n) |
| Ro'yxatni ag'darish | 3 ko'rsatkich | O(n) | O(1) |
| Ro'yxat o'rtasi | tez/sekin | O(n) | O(1) |
| Sikl | Set bilan | O(n) | O(n) |
| Sikl | Floyd | O(n) | O(1) |
| Birlashtirish | dummy head | O(n + m) | O(1) |
| Oxiridan n-chi | masofali 2 ko'rsatkich | O(n) | O(1) |

git add 14/MURAKKABLIK.md 14/17-royxat-masalalari
git commit -m "14/17: linked list masalalari va testlar"

10. Real ishda

• Xatoni aniqlash. Floyd usuli faqat ro'yxatda emas: "keyingisi" funksiyasi bor har qanday ketma-ketlikda sikl topadi — tasodifiy sonlar generatorining davri, takrorlanuvchi holatlar, havolalar zanjiri.
• Birlashtirish. Ikki saralangan oqimni birlashtirish — Merge sort ning yuragi va ma'lumotlar bazalarida katta fayllarni saralashning asosi.
• Doubly list. Brauzer tarixi ("orqaga" va "oldinga"), matn muharrirlaridagi qatorlar, LRU kesh. Java'ning LinkedList klassi va Python'ning collections.deque ichida ham ikki tomonlama bog'langan tuzilma bor.
• Intervyu. "Reverse Linked List" (LeetCode 206), "Middle of the Linked List" (876), "Linked List Cycle II" (142), "Merge Two Sorted Lists" (21), "Remove Nth Node From End" (19) — eng mashhur beshlik.

Xulosa

• Ag'darish: saqla → bur → sur. Uchta ko'rsatkich, O(n) vaqt, O(1) xotira; rekursiv variant O(n) stek.
• Tez (2 qadam) va sekin (1 qadam) ko'rsatkich: tez oxiriga yetganda sekin o'rtada. Shart: fast !== null && fast.next !== null.
• Floyd: sikl bo'lsa tez sekinni quvib yetadi; ikkinchi bosqich sikl boshini topadi. Set dan ≈ 25 baravar tez, O(1) xotira.
• Dummy head boshni o'zgartiradigan holatlarni oddiy holatga aylantiradi: oxirida dummy.next qaytaring.
• Doubly list ma'lum tugunni O(1) da o'chiradi (Map bilan — LRU asosi); circular list round-robin uchun, lekin null siz — to'xtash shartini o'zingiz qo'ying.

Keyingi dars: Stack (LIFO) — oxirgi kirgan birinchi chiqadi: qavslar muvozanati, "bekor qilish" (undo) va ifodani hisoblash.

Manbalar

• Donald E. Knuth, "The Art of Computer Programming", 2-jild, 3-nashr, 1997 — 3-bob, tasodifiy sonlar davri haqidagi mashqlar (Floyd sikl aniqlash usuli).
• Robert W. Floyd usuli va Brent varianti: Richard P. Brent, "An improved Monte Carlo factorization algorithm", BIT, 1980.
• LeetCode: 206, 876, 142, 21, 19 — leetcode.com/problems