40 parimat lingitud nimekirjaga intervjuuküsimust ja vastust (2026)

Autor: Sarah Chen Sarah Chen
Hours Ajakohastatud

Enim lingitud intervjuuküsimused ja vastused

Andmestruktuuride intervjuuks valmistumine nõuab keskendumist väljakutsetele. Seotud loendiga intervjuuküsimused näitavad probleemide lahendamise sügavust, pointerloogikat, mäluteadlikkust ja seda, kuidas kandidaadid äärmuslike juhtumite üle arutlevad.

Lingitud loendite valdamine avab töökohti tootemeeskondades, platvormidel ja süsteemitehnikas. Praktiline kogemus arendab tugevat tehnilist oskusteavet, analüütilist mõtlemist ja selgeid kodeerimisharjumusi. Alates algajatest kuni kogenud spetsialistideni toetab see oskustepagas reaalset silumist, jõudlusanalüüsi, nooremate juhendamist ja koostööd juhtidega skaleeritavate lahenduste väljatöötamisel, kasutades kogemustest lähtuvaid täiustatud kontseptsioone. Loe rohkem…

👉 Tasuta PDF-i allalaadimine: Lingitud nimekirja intervjuuküsimused ja vastused

Enim lingitud intervjuuküsimused ja vastused

1) Selgita, mis on lingitud loend ja kuidas see erineb massiivist.

A lingitud loend on lineaarne andmestruktuur, kus elemendid, mida nimetatakse sõlmedeks, on ühendatud pointerite või viidete abil. Iga sõlm sisaldab andmeid ja pointerit/viidet loendi järgmisele sõlmele. Erinevalt massiividest ei salvesta lingitud loendid elemente külgnevas mälus.

Lingitud loendi ja massiivi peamised erinevused:

tunnusjoon Lingitud loend Array
Mälu eraldamine Dünaamiline Staatiline
Elemendi juurdepääsu aeg O (n) O (1)
Lisamine/kustutamine Tõhus (igas asendis) Kallis (vajab ümberpaigutamist)
Ülemine mälu Lisaruumi kursorite jaoks Lisakursorit pole vaja

Kokkuvõttes pakuvad lingitud loendid kompromissi kiirema lisamise ja dünaamilise suuruse muutmise vahel, et saavutada aeglasem juhuslik juurdepääs ja pointerite tõttu suurem mälukoormus.

2) Millised on erinevad lingitud loendite tüübid?

Seal on mitut tüüpi lingitud loendeidja intervjueerijad paluvad teil sageli nende vahel vahet teha:

  • Üksikult lingitud loend: Iga sõlm osutab ainult järgmisele sõlmele.
  • Topeltlingitud loend: Sõlmedel on kaks pointerit: üks järgmise ja üks eelmise sõlme juurde.
  • Ringjalt seotud nimekiri: Viimane sõlm osutab tagasi esimesele sõlmele, moodustades silmuse.
  • Kahekordselt ringikujuline lingitud nimekiri: Kombineerib nii ringloendeid kui ka kahekordselt lingitud loendeid.

Igal tüübil on erinevad kasutusjuhud, mis põhinevad läbimis- ja mäluvajadusel. Näiteks kahekordselt lingitud loendid võimaldavad lihtsat tagasisuunas läbimist lisaviidete hinnaga.

3) Kuidas pöörata üksikult lingitud loendit tagurpidi? (kodeerimismeetod)

RevLingitud loendi loomine on klassikaline intervjuuküsimus. Eesmärk on muuta pointerite suunda nii, et loend pööratakse kohapeal ümber ilma uusi sõlmi eraldamata.

Põhiidee:
Kasutage kolme näpunäidet — prev, currja next — ja korrake nimekirja läbi. Igal sammul suunake ümber curr.next et prev, seejärel liigutage kõiki pointereid edasi.

ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;
    while (curr != null) {
        ListNode next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    return prev; // New head
}

See teisendab lingitud struktuuri ilma lisaruumita ja käivitub O (n) aega.

4) Selgitage kahepunktilist meetodit lingitud loendi keskpunkti leidmiseks.

Lingitud loendi keskmise sõlme leidmiseks on kõige tõhusam viis kasutada kahte pointerit:

  • A aeglane osuti liigutab korraga ühte sõlme.
  • A kiire osuti liigutab korraga kahte sõlme.

Kui kiire osuti jõuab lõppu, on aeglane osuti keskpunktis. See tehnika töötab järgmiselt: O (n) aeg ilma lisaruumita.

5) Kuidas tuvastada tsüklit lingitud loendis?

Tsükli tuvastamine on veel üks klassikaline probleem. Standardlahendus kasutab Floydi kilpkonna ja jänese algoritm:

  • Liikuma slow pointer üks samm korraga.
  • Liikuma fast pointer kaks sammu korraga.
  • Kui loendis on tsükkel, siis kaks pointerit kohtuvad.

Kui kiire osuti jõuab null, loendil pole tsüklit. See meetod töötab O (n) aeg ja O (1) ruumi.

6) Millised on seotud loendite eelised ja puudused?

Lingitud loendid pakuvad mitmeid eeliseid ja kompromisse:

Eelised Puudused
Dünaamiline suurus Juhuslikku juurdepääsu pole
Lihtne sisestamine/kustutamine Lisamälu pointerite jaoks
Tõhus kasvavate andmete jaoks Halb vahemälu jõudlus

Lingitud loendid toimivad dünaamiliste andmete puhul hästi, kuid elementide ligipääsuks võivad need olla aeglasemad kui massiivid, kuna iga ligipääs nõuab päisest läbimist.

SEOTUD ARTIKLID

7) Kuidas ühendada kahte sorteeritud lingitud loendit?

Kahe sorteeritud loendi ühendamine on veel üks levinud intervjuuprobleem. Idee seisneb mõlemas loendis samaaegselt ringi käimises ja uue sorteeritud loendi loomisel, valides igal sammul kummastki loendist väiksema sõlme.

ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    ListNode tail = dummy;
    while (l1 != null && l2 != null) {
        if (l1.val < l2.val) {
            tail.next = l1;
            l1 = l1.next;
        } else {
            tail.next = l2;
            l2 = l2.next;
        }
        tail = tail.next;
    }
    tail.next = (l1 != null) ? l1 : l2;
    return dummy.next;
}

See meetod säilitab sorteeritud järjestuse ja töötab O(n + m) pikkustega n ja m loendite aeg.

8) Selgitage, kuidas kustutada lingitud loendi lõpust N-ndat sõlme.

Kõige tõhusam tehnika kasutamine kaks pointerit n sõlme võrra eraldatud. Liiguta esimest pointerit n sammu võrra edasi, seejärel liiguta mõlemat pointerit, kuni esimene jõuab lõppu. Teine pointer asub siis vahetult enne sihtsõlme.

See väldib loendi pikkuse eraldi arvutamist ja lõpetab O (n) aeg. See käsitleb ka äärejuhtumeid, näiteks esimese sõlme eemaldamist.

9) Milline on aja keerukus lingitud loendi k-nda elemendi juurde pääsemiseks?

Juurdepääs kLingitud loendi element nõuab läbimist algusest kuni elemendini. k. sõlme. Kuna lingitud loendid ei paku otsest indekseerimist, maksab see O (n) halvimal juhul aeg.

Seevastu massiivid toetavad otsest indekseerimist O (1) aega.

10) Miks peaks massiivi asemel kasutama lingitud loendit?

Lingitud loendid on eriti kasulikud järgmistel juhtudel:

  • Sa ootad sagedasi lisamisi ja kustutamisi suvalistes positsioonides.
  • Sa ei tea oma andmete suurust ette.
  • Mälu fragmenteerumine muudab külgneva mälu jaotamise keeruliseks.

Need toetavad tõhusat dünaamilist mälujaotust ja konstantse aja sisestamist/kustutamist loendi lõpus või teadaoleva sõlme viitega – eelised, millele massiivid ei suuda vastata.

11) Millised on seotud loendite reaalsed rakendused?

Lingitud loendeid kasutatakse laialdaselt süsteemides, kus dünaamiline mälu eraldamine, sagedased lisamisedvõi muutuva suurusega andmestruktuurid on vajalikud. Neid rakendatakse mitmetes arvutiteaduse põhikontseptsioonides ja rakendustes, näiteks:

  • Dünaamiline mäluhaldus (kasutatakse operatsioonisüsteemides)
  • Tagasivõtmise/Uuesti tegemise funktsioonid tekstiredaktorites
  • Räsitabeli aheldamine kokkupõrgete lahendamiseks
  • Muusika- või videoesitusloendi navigeerimine
  • Graafi külgnevuse esitus
  • Polünoomsed aritmeetilised tehted

Need näited toovad esile, kuidas lingitud loendid pakuvad paindlikkust ja tõhusat järjestuste manipuleerimist olukorras, kus massiivi suuruse muutmine oleks kulukas.

12) Selgitage ühe- ja kahekordselt lingitud loendi erinevust.

tunnusjoon Üksiklingitud loend Topeltlingitud loend
viiteid 1 (ainult järgmine sõlm) 2 (eelmine ja järgmine)
Läbisõit Ainult ühes suunas Mõlemad suunad
Memory Usage Less (ainult üks pointer) Rohkem (lisaviide)
kustutamine Raskem (vaja eelmist sõlme) Lihtsam
Kasutamise näide Stacki rakendamine Brauseri ajaloo navigeerimine

A kahekordselt lingitud loend on mitmekülgsem, aga tarbib rohkem mälu. Seevastu üksikult lingitud loendid on kerged ja tõhusad ühesuunaliseks liikumiseks.

13) Kuidas eemaldada duplikaate sorteeritud lingitud loendist?

Kui lingitud loend on juba sorteeritud, asuvad duplikaadid külgnevalt.

Käi loend läbi ja võrdle iga sõlme andmeid järgmise sõlme andmetega. Kui need sobivad, jäta järgmine sõlm vahele.

void removeDuplicates(ListNode head) {
    ListNode current = head;
    while (current != null && current.next != null) {
        if (current.val == current.next.val) {
            current.next = current.next.next;
        } else {
            current = current.next;
        }
    }
}

Keerukus: Aeg O(n) ja ruum O(1).

Sorteerimata loendite puhul saab nähtud väärtuste jälgimiseks kasutada HashSeti.

14) Mis vahe on lineaarsel ja ringlinkitud loendil?

tunnusjoon Lineaarne seotud nimekiri Ringikujuline lingitud loend
Viimane sõlm Punktid NULL-ile Peasõlme suunas osutab
Läbisõit Lõpeb, kui next == NULL Pidev läbimine
Kasuta Case'it Stack, järjekord Ringgraafiku koostamine
Keerukus Lihtsam Keerulisem käsitsemine

Ringloendid on eriti kasulikud sellistes rakendustes nagu protsessori ajastamine, kus protsesse tsükliliselt käivitatakse.

15) Kuidas leida kahe lingitud loendi lõikepunkt?

Kahe üksikult lingitud loendi lõikumise kindlakstegemiseks toimige järgmiselt.

  1. Leia mõlema loendi pikkused.
  2. Liiguta pikema loendi kursorit pikkuste vahe võrra edasi.
  3. Käi mõlemat nimekirja samaaegselt läbi, kuni sõlmed on identsed.

Teine võimalus on: a Räsikomplekt saab kasutada külastatud sõlmede salvestamiseks O(n) ruumi jaoks.

See lähenemisviis on tõhus ja seda küsitakse sageli kõrgema taseme intervjuudel.

16) Kuidas kontrollida, kas kaks lingitud loendit on identsed?

Kaks lingitud loendit on identsed, kui:

  • Neil on sama arv sõlmi.
  • Vastavad sõlme väärtused on järjekorras identsed.

Algoritm:

  1. Käi mõlemad nimekirjad koos läbi.
  2. Võrdle iga sõlme andmeid.
  3. Kui kõik paarid sobivad kokku ja mõlemad jõuavad NULL-ini, on nad identsed.

Ajaline keerukus: O (n)

Ruumi keerukus: O (1)

17) Mis on mäluleke lingitud loendite kontekstis?

A mäluleke tekib siis, kui dünaamiliselt eraldatud sõlmi pärast kasutamist ei vabastata.

Lingitud loendites, kui delete or free() Kui loendist eemaldatud sõlmede puhul ei kutsuta seda välja, jääb mälu hõivatuks, isegi kui see pole enam ligipääsetav.

Näiteks kustutatud sõlmede vabastamata jätmine C/-sC++ viib mälu järkjärgulise ammendumiseni, mis omakorda aeglustab süsteemi või põhjustab selle krahhe.

Nõuetekohane puhastamine destruktori või selgesõnalise eraldamise abil aitab seda probleemi vältida.

18) Selgitage, kuidas rakendada pinu lingitud loendi abil.

Aastal Kestab, elemendid järgivad LIFO (viimane sisse, esimene välja) järjekorda.

Lingitud loend on ideaalne, kuna lisamised ja kustutamised toimuvad tõhusalt loendi alguses.

Operatused:

  • Push: Lisa uus sõlm pähe.
  • Pop: Eemalda sõlm peast.
  • Piilu: Tagasta pea andmed.

Plussid:
Pole vaja fikseeritud suurusega massiivi; kasvab elementide lisamisel dünaamiliselt.

19) Kuidas saab lingitud loendit kasutada järjekorra loomiseks?

Aastal järjekorda, elemendid järgivad FIFO (esimesena sisse, esimesena välja) järjekorda.

Kasutage lingitud loendit, kus:

  • Järjekorda lisamine (sisestamine): Lisa sabale sõlm.
  • Eemalda järjekorrast: Kustuta sõlm päisest.

See võimaldab mõlemat toimingut O (1) aeg kahe näitajaga — front ja rear.

Seda kasutatakse tavaliselt protsesside ajastamisel ja printerijärjekorra süsteemides.

20) Millised on massiiviloendi ja lingitud loendi erinevused? Java?

Aspekt ArrayList Lingitud nimekiri
Säilitamine Dünaamiline massiiv Kahekordselt lingitud loend
Juurdepääsuaeg O (1) O (n)
Lisa/Kustuta Keskmiselt kallis Tõhus otsas
Ülemine mälu Less Rohkem (lisajuhiseid)
Kasuta Case'it Sagedane juurdepääs Sagedane sisestamine/kustutamine

Näide: Kasutama ArrayList otsingumahukate toimingute jaoks ja LinkedList kui domineerivad sisestamise/kustutamise operatsioonid.

21) Kuidas mitmetasandilist lingitud loendit lamendada?

A mitmetasandiline lingitud loend võivad sisaldada sõlmi, millel on mõlemad next ja child pointerid (iga laps viib teise lingitud loendini). Eesmärk on kõik sõlmed ühetasandiliseks lingitud loendiks lamendada.

Lähenemisviis:

  1. Kasutama Kestab or rekursiivne funktsioon.
  2. Alusta peasõlmest.
  3. Kui sõlmel on child, lükake selle next sõlm pinu külge ja tee child as next.
  4. Jätka, kuni virn on tühi.

Aja keerukus: O (n)

Ruumi keerukus: O(n) rekursiooni/pinu jaoks.

Näide (kontseptuaalselt):

1 - 2 - 3
    |
    4 - 5
Flattened → 1 → 2 → 4 → 5 → 3

See küsimus hindab teie arusaama rekursioonist ja pointeri manipuleerimisest.

22) Kuidas kloonida lingitud loendit juhuslike pointeritega?

Igal selle spetsiaalse lingitud loendi sõlmel on kaks pointerit:

  • next → osutab järgmisele sõlmele.
  • random → osutab mis tahes suvalisele sõlmele.

Algoritm (3 sammu):

  1. Lisa kloonitud sõlmed algsete sõlmede vahele.
  2. Määrake kloonidele juhuslikud pointerid (clone.random = original.random.next).
  3. Eraldage need kaks nimekirja.

See väldib räsikaardi jaoks lisaruumi ja töötab O (n) aeg koos O (1) lisaruumi.

Kasutusjuhtum: Keeruliste andmestruktuuride (nt graafikute või objektiviidete) süvakopeerimine.

23) Mis on vahelejätmisloend ja kuidas see on seotud lingitud loenditega?

A vahelejätmise nimekiri on kihiline lingitud loendistruktuur, mis võimaldab kiiret otsingut, sisestamist ja kustutamist (sarnaselt tasakaalustatud puudega).

Operamine Keskmine aeg Halvimal juhul
Otsing O (log n) O (n)
Lisa/Kustuta O (log n) O (n)

See sisaldab mitut taset, kus ülemised tasemed "vahele jätavad" mitu sõlme, parandades otsingu efektiivsust.

Näide: Kasutatakse andmebaasides nagu Redis ja samaaegsetes kaardirakendustes.

24) Kuidas tuvastada palindroomi lingitud loendis?

Lingitud loend on palindroom, kui see loeb sama nii tagasi kui ka edasi.

Algoritm:

  1. Leia nimekirja keskpaik.
  2. Revmuide teine ​​pool.
  3. Võrdle kahte poolt sõlme haaval.

Kui kõik vastavad sõlmed sobivad kokku, on tegemist palindroomiga.

Näide:

1 → 2 → 3 → 2 → 1 → ✅ Palindroom

1 → 2 → 3 → 4 → ❌ Ei ole palindroom

Aja keerukus: O (n)

Ruumi keerukus: O (1)

25) Kuidas eemaldada lingitud loendist tsükkel?

Kui silmus on olemas (kasutades Floydi tsükli tuvastamist), eemaldage see järgmiste sammude abil:

  1. Tuvastage aeglaste ja kiirete pointerite kohtumispunkt.
  2. Liiguta üks kursor pähe.
  3. Liiguta mõlemat kursorit sammhaaval, kuni nad kohtuvad tsükli algussõlm.
  4. Määra eelmise sõlme next et null.

See lähenemisviis tagab, et tsüklite lahendamisel ei kasutata lisamälu.

26) Millised on erinevad viisid lingitud loendite esitamiseks mälus?

Lingitud loendeid saab esitada kujul kolm peamist viisi:

Esindustüüp Kirjeldus Kasutamise näide
Dünaamilised sõlmed Iga sõlm eraldatakse ja lingitakse dünaamiliselt C, C++
Staatiline massiivi esitus Kasutab pointerite asemel massiiviindekseid Manustatud süsteemid
Lingitud objektid Objektorienteeritud esitus klassidega Java, Python

Iga lähenemisviis sobib erinevatele keskkondadele – näiteks massiivipõhiseid loendeid kasutatakse siis, kui pointeri manipuleerimine on piiratud.

27) Kuidas leida lingitud loendi pikkust (iteratiivset ja rekursiivset)?

Iteratiivne lähenemine:

int getLength(ListNode head) {
    int count = 0;
    while (head != null) {
        count++;
        head = head.next;
    }
    return count;
}

Rekursiivne lähenemine:

int getLength(ListNode head) {
    if (head == null) return 0;
    return 1 + getLength(head.next);
}

Mõlemal lähenemisviisil on O (n) ajaline keerukus; rekursioon lisab O (n) kõnepinu tõttu ruumi lisakulu.

28) Selgitage näite abil ringselt kahekordselt lingitud loendite mõistet.

Aastal ringikujuline kahekordselt lingitud loend, igal sõlmel on kaks linki – üks järgmise ja teine ​​eelmisega – ning viimase sõlme next osutab pähe, samal ajal kui pea prev osutab viimasele sõlmele.

Näidiskasutusjuhtumid:

  • Reaalajas operatsioonisüsteemid (ringjada ajastamine)
  • Muusika esitusloendi kordumine
  • Vahelehtede või slaidide vahel navigeerimine

Plussid:

  • Kahesuunaline läbimine.
  • Nullviiteid pole.
  • Tõhusad lisamised ja kustutamised.

29) Kuidas kustutada lingitud loendist alternatiivseid sõlmi?

Algoritm:

  1. Alusta peast.
  2. Kustuta iga teine ​​sõlm pointereid kohandades.
  3. Jätkake, kuni nimekiri lõpeb.

Näide:

Input: 1 → 2 → 3 → 4 → 5  
Output: 1 → 3 → 5

Keerukus:

  • Aeg: O(n)
  • Tühik: O(1)

See kontrollib pointeri läbimise ja kustutamise ohutuse mõistmist.

30) Kuidas leida lingitud loendi algusest ja lõpust n-nda sõlme?

Algusest peale: Käi nimekirja läbi, kuni arv = n.

Lõpust peale: Kasutage kahte näpunäidet.

  1. Liiguta esimest kursorit n sammu võrra ettepoole.
  2. Liiguta mõlemat samaaegselt, kuni esimene jõuab nullini.
  3. Teine pointer osutab nüüd n-ndale sõlmele lõpust.

Aja keerukus: O (n)

Ruumi keerukus: O (1)

See lähenemisviis väldib pikkuse eraldi arvutamist, parandades efektiivsust.

31) Kuidas lingitud loendit ümber järjestada?

Probleem: Antud on nimekiri L0 → L1 → … → Ln-1 → Ln, järjesta see ümber järgmiselt L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …

Sammud:

  1. Leia nimekirja keskpaik.
  2. Revmuide teine ​​pool.
  3. Ühenda kaks poolt vaheldumisi.

Näide:

Input: 1 → 2 → 3 → 4 → 5  
Output: 1 → 5 → 2 → 4 → 3

Keerukus: Aeg O(n), ruum O(1).

See testib ühes küsimuses mitut lingitud loendi toimingut.

32) Kuidas jaotada lingitud loend antud väärtuse x ümber?

Eesmärk:
Järjesta sõlmed ümber nii, et kõik x-st väiksemad sõlmed paikneksid enne x-st suuremaid või sellega võrdseid sõlmi.

Lähenemisviis:

  • Pea kahte näidisloendit: before ja after.
  • Käi läbi algne loend ja lisa sõlmed vastavatele loenditele.
  • Lõpus ühendage need.

Näide:

Input: 3 → 5 → 8 → 5 → 10 → 2 → 1, x = 5  
Output: 3 → 2 → 1 → 5 → 8 → 5 → 10

Seda küsitakse sageli andmete ümberkorraldamise võime hindamiseks.

33) Kuidas lingitud loendit sorteerida?

Kuna lingitud loendid ei toeta juhuslikku juurdepääsu, Ühenda sortimine on parim valik.

Sammud:

  1. Jaga nimekiri pooleks, kasutades aeglaseid/kiireid pointereid.
  2. Sorteeri iga pool rekursiivselt.
  3. Ühenda sorteeritud pooled.

Plussid:

  • O(n log n) aeg.
  • O(1) lisaruum (iteratiivse versiooni jaoks).

Erinevalt massiividest on QuickSort lingitud loendite puhul pointeri ümberpaigutamise keerukuse tõttu ebaefektiivne.

34) Mis vahe on ühe-, kahe- ja ringlingitud loenditel?

tunnusjoon Üksikult Kahekordselt Ringkiri
Lingid Üks (järgmine) Kaks (eelmine ja järgmine) Viimane sõlm ühendub peaga
Läbisõit Ainult edasi Edasi ja tagasi Lõpmatu läbimine võimalik
Lisamine/kustutamine Mõõdukas Lihtsam mõlemast otsast Erijuhtumite käsitlemine
Kasuta Case'it Stack, järjekord Toimingute tagasivõtmine Ringgraafiku koostamine

See võrdlusküsimus näib sageli kontrollivat kontseptuaalset selgust.

35) Kuidas leida kahe ringikujuliselt seotud loendi lõikepunkt?

See on ristmike probleemi laiendus.

Algoritm:

  1. Tuvasta, kas igas loendis on tsükkel.
  2. Kui mõlemad on atsüklilised → kasutage standardset ristumisalgoritmi.
  3. Kui mõlemad on tsüklilised → leia mõlema tsükli alguspunkt ja kontrolli, kas need on samad või ühendatud.

See probleem ühendab tsükli tuvastamine ja ristmike loogika, mitmemõistelise arutluskäigu testimine.

36) Selgitage, kuidas lisada sõlme sorteeritud lingitud loendisse.

Sammud:

  1. Looge antud väärtusega uus sõlm.
  2. Liigu edasi, kuni leiad õige asendi.
  3. kohandama next vastavalt vihjeid.

Näide:

Input: 1 → 3 → 5 → 7, Insert 4  
Output: 1 → 3 → 4 → 5 → 7

See on elementaarne manipuleerimisülesanne osuti reguleerimise mõistmise testimiseks.

37) Kuidas jagada lingitud loend kaheks pooleks?

Algoritm:

  • Kasutage aeglase ja kiire pointeri meetodit.
  • Kui fast jõuab lõppu, slow asub keskpunktis.
  • Jaga selles sõlmes.

Näide:

Input: 1 → 2 → 3 → 4 → 5  
Output: 1 → 2 → 3  and  4 → 5

See toiming on sageli lingitud loendi ühendamise sortimise esimene samm.

38) Kuidas leida väärtuse viimane esinemiskoht lingitud loendis?

Liigu nimekirjas läbi, jälgides samal ajal viimast sõlme, kust sihtväärtus leitakse.

Pseudokood:

ListNode findLastOccurrence(ListNode head, int val) {
    ListNode result = null;
    while (head != null) {
        if (head.val == val) result = head;
        head = head.next;
    }
    return result;
}

Keerukus: O (n)

See kontrollib lineaarse läbimise ja seisundikontrolli mõistmist.

39) Kuidas saab lingitud loendist eemaldada kõik antud võtme esinemised?

Algoritm:

  1. Käsitle peasõlmi esmalt, kui need sisaldavad sihtvõtit.
  2. Seejärel läbige ja kustutage järgmised võtit sisaldavad sõlmed.

Näide:

Input: 1 → 2 → 6 → 3 → 4 → 5 → 6, Key = 6  
Output: 1 → 2 → 3 → 4 → 5

Keerukus: O (n)

See näitab teadmisi äärmusjuhtudest (eriti pea kustutamisest).

40) Millised on peamised erinevused pinu- ja lingitud loendi andmestruktuuride vahel?

tunnusjoon Stack Lingitud loend
Juurdepääsu tüüp LIFO (viimane sisse, esimene välja) Järjestikune
Täitmine Massiiv või lingitud loend Sõlmepõhine
Operamine Lükka/Pagu Lisa/Kustuta/Liigu
Paindlikkus Piiratud juurdepääs Paindlik juurdepääs
Kasuta Case'it Funktsioonikõnede haldamine Dünaamiline andmetöötlus

Stacki saab rakendada lingitud loendi kasutamine, kuid need erinevad kontseptsiooni poolest – pinul on piiratud juurdepääs, samas kui lingitud loend on üldotstarbeline struktuur.

🔍 Enim lingitud intervjuuküsimuste nimekiri koos reaalsete stsenaariumide ja strateegiliste vastustega

1) Mis on lingitud loend ja mille poolest see erineb massiivist?

Kandidaadilt oodatakse: Intervjueerija soovib hinnata teie arusaamist põhilistest andmestruktuuridest ja teie võimet võrrelda kompromisse.

Näite vastus: Lingitud loend on lineaarne andmestruktuur, kus elemendid, mida nimetatakse sõlmedeks, on ühendatud pointerite abil. Iga sõlm sisaldab andmeid ja viidet järgmisele sõlmele. Erinevalt massiividest ei vaja lingitud loendid külgnevat mälu ja võimaldavad dünaamilist suuruse muutmist, kuid neil on aeglasem juurdepääsuaeg, kuna elemente ei indekseerita.

2) Millal valiksite reaalses rakenduses massiivi asemel lingitud loendi?

Kandidaadilt oodatakse: Nad hindavad teie praktilist otsustusvõimet sobivate andmestruktuuride valimisel.

Näite vastus: Lingitud loendi valiksin siis, kui on vaja sageli sisestada ja kustutada, eriti andmestiku keskel. Eelmisel ametikohal töötasin ülesannete ajastamise funktsiooni kallal, kus ülesandeid lisati ja eemaldati sageli ning lingitud loend pakkus paremat jõudlust kui massiiv.

3) Kas saate selgitada erinevust üksikult ja kahekordselt lingitud loendite vahel?

Kandidaadilt oodatakse: Intervjueerija soovib kontrollida teie kontseptuaalset selgust ja võimet tehnilisi erinevusi selgelt selgitada.

Näite vastus: Ühekordselt lingitud loendil on sõlmed, mis osutavad ainult järgmisele sõlmele, samas kui kahekordselt lingitud loendil on sõlmed, mis osutavad nii järgmisele kui ka eelmisele sõlmele. Kahekordselt lingitud loendid võimaldavad lihtsamat tagasiliikumist, kuid vajavad lisakursori tõttu rohkem mälu.

4) Kuidas tuvastada tsüklit lingitud loendis?

Kandidaadilt oodatakse: See paneb proovile teie probleemide lahendamise oskused ja tuttavuse levinud algoritmiliste mustritega.

Näite vastus: Levinud lähenemisviis on kasutada kahte erineva kiirusega liikuvat pointerit, mida sageli nimetatakse aeglase ja kiire pointeri tehnikaks. Tsükli olemasolul need kaks pointerit lõpuks kohtuvad. Eelmises positsioonis kasutasin seda lähenemisviisi andmetöötlustorustikus lõpmatute tsüklite vältimiseks.

5) Milliseid levinumaid toiminguid lingitud loenditega tehakse?

Kandidaadilt oodatakse: Intervjueerija tahab näha, kas sa mõistad standardseid toiminguid ja nende tagajärgi.

Näite vastus: Levinud toimingute hulka kuuluvad loendi sisestamine, kustutamine, läbimine, otsimine ja tagasipööramine. Igal toimingul on erinev ajaline keerukus olenevalt sellest, kus seda tehakse, mis on oluline tõhusate süsteemide loomisel.

6) Kuidas toimida sõlme lisamisega lingitud loendi keskele?

Kandidaadilt oodatakse: Nad kontrollivad teie arusaamist pointeri manipuleerimisest ja tähelepanu detailidele.

Näite vastus: Keskele sõlme lisamiseks käin kõigepealt loendi läbi, et leida sihtpositsioon, seejärel kohandan pointereid nii, et uus sõlm osutaks järgmisele sõlmele ja eelmine sõlm uuele sõlmele. Pointerite hoolikas uuendamine on kriitilise tähtsusega, et vältida loendi purunemist.

7) Kirjeldage olukorda, kus lingitud loend põhjustas jõudlusprobleeme, ja kuidas te selle lahendasite.

Kandidaadilt oodatakse: See käitumuslik küsimus hindab teie võimet analüüsida ja optimeerida.

Näite vastus: Eelmisel töökohal kasutati sagedaste otsinguoperatsioonide jaoks lingitud loendit, mis aeglustas jõudlust. Tuvastasin probleemi ja soovitasin minna üle räsipõhisele struktuurile, mis parandaks otsinguaega oluliselt.

8) Kuidas lingitud loendit ümber pöörata?

Kandidaadilt oodatakse: Intervjueerija testib teie loogilist mõtlemist ja iteratiivsete või rekursiivsete lähenemisviiside mõistmist.

Näite vastus: Ma pööraksin lingitud loendi tagurpidi, itereerides seda läbi ja muutes iga sõlme järgmise pointeri osutama eelmisele sõlmele. See protsess jätkub seni, kuni kõik pointerid on tagurpidi pööratud ja loendi päis on uuendatud.

9) Millised on lingitud loendite kasutamise eelised ja puudused?

Kandidaadilt oodatakse: Nad tahavad tasakaalustatud vaatenurka ja teadlikkust kompromissidest.

Näite vastus: Eeliste hulka kuuluvad dünaamiline suurus ning tõhusad lisamised ja kustutamised. Puudusteks on suurem mälukasutus ja aeglasemad juurdepääsuajad võrreldes massiividega. Minu viimases rollis aitas nende kompromisside mõistmine valida erinevate komponentide jaoks õige struktuuri.

10) Kuidas otsustada, millist tüüpi lingitud loendit süsteemi kujundamisel kasutada?

Kandidaadilt oodatakse: See situatsiooniküsimus hindab otsuste langetamist arhitektuurilises kontekstis.

Näite vastus: Ma arvestan selliste teguritega nagu läbimisvajadus, mälupiirangud ja toimingute sagedus. Näiteks kui on vaja tagasi läbida, on sobivam kahekordselt lingitud loend, samas kui lihtsamate ja mälusäästlike rakenduste jaoks piisab ühekordselt lingitud loendist.

Võta see postitus kokku järgmiselt: