40 parasta linkitetyn listan haastattelukysymystä ja vastausta (2026)

by: Sarah Chen Sarah Chen
Hours Päivitetty

Haastattelukysymykset ja vastaukset linkitettyjen listalla

Tietorakenteiden haastatteluun valmistautuminen vaatii keskittymistä haasteisiin. Linkitettyjen luetteloiden haastattelukysymykset paljastavat ongelmanratkaisukyvyn syvyyttä, osoittimen logiikkaa, muistitietoisuutta ja sitä, miten ehdokkaat päättelevät reunatapausten läpi.

Linkitettyjen luetteloiden hallinta avaa rooleja tuotetiimeissä, alustoilla ja järjestelmäsuunnittelussa. Käytännön kokemus kehittää vahvaa teknistä asiantuntemusta, analyyttistä ajattelua ja selkeitä koodaustapoja. Aloittelijoista kokeneisiin ammattilaisiin tämä taitopaketti tukee todellista virheenkorjausta, suorituskykyanalyysia, juniorien mentorointia ja yhteistyötä esimiesten kanssa skaalautuvien ratkaisujen parissa kokemuksesta saatujen edistyneiden konseptien avulla. Lue lisää ...

👉 Ilmainen PDF-lataus: Linkitettyjen listan haastattelukysymykset ja vastaukset

Haastattelukysymykset ja vastaukset linkitettyjen listalla

1) Selitä, mikä on linkitetty lista ja miten se eroaa taulukosta.

A linkitetty luettelo on lineaarinen tietorakenne, jossa elementit, joita kutsutaan solmuiksi, on yhdistetty osoittimilla tai viittauksilla. Jokainen solmu sisältää dataa ja osoittimen/viittauksen listan seuraavaan solmuun. Toisin kuin taulukot, linkitetyt listat eivät tallenna elementtejä yhtenäiseen muistiin.

Linkitetyn listan ja taulukon keskeiset erot:

Ominaisuus Linkitetty luettelo Ryhmä
Muistin varaus Dynaaminen Staattinen
Elementin käyttöaika O (n) O (1)
Lisäys/Poisto Tehokas (missä tahansa asennossa) Kallis (tarvitsee siirron)
Ylimääräinen muisti Lisätilaa osoittimille Ei ylimääräistä osoittimen yläpuolella

Yhteenvetona voidaan todeta, että linkitetyt listat tarjoavat kompromissin nopeammista lisäyksistä ja dynaamisesta koon muuttamisesta hitaamman satunnaiskäytön ja osoittimien aiheuttaman lisämuistin kustannuksen hyväksi.

2) Mitä erilaisia ​​linkitettyjä listoja on olemassa?

On useita linkitettyjen listojen tyyppejä, ja haastattelijat usein pyytävät sinua erottamaan ne toisistaan:

  • Yksinkertaisesti linkitetty lista: Jokainen solmu osoittaa vain seuraavaan solmuun.
  • Kaksoislinkitetty lista: Solmuilla on kaksi pistettä: yksi seuraavaan ja yksi edelliseen solmuun.
  • Ympyräsidottu lista: Viimeinen solmu osoittaa takaisin ensimmäiseen solmuun muodostaen silmukan.
  • Kaksinkertaisesti ympyrälinkitetty lista: Yhdistää sekä ympyränmuotoiset että kaksinkertaisesti linkitetyt listat.

Jokaisella tyypillä on omat käyttötapauksensa läpikulun ja muistintarpeiden perusteella. Esimerkiksi kaksinkertaisesti linkitetyt listat mahdollistavat helpon taaksepäin kulkemisen ylimääräisten osoittimien hinnalla.

3) Miten käännät yksinkertaisesti linkitettyjen listan? (koodausmenetelmä)

RevLinkitetyn listan luominen on klassinen haastattelukysymys. Tavoitteena on muuttaa osoittimien suuntaa siten, että lista kääntyy paikoilleen ilman uusien solmujen allokointia.

Keskeinen idea:
Käytä kolmea osoitinta — prev, currja next — ja käy lista läpi iteroimalla. Jokaisessa vaiheessa ohjaa curr.next että prevja siirrä sitten kaikkia osoittimia eteenpäin.

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
}

Tämä muuttaa linkitetyn rakenteen ilman lisätilaa ja toimii O (n) ajan.

4) Selitä kahden osoittimen tekniikka linkitetyn listan keskikohdan löytämiseksi.

Tehokkain tapa löytää linkitetyn listan keskimmäinen solmu on käyttää kahta osoitinta:

  • A hidas osoitin siirtää yhden solmun kerrallaan.
  • A nopea osoitin siirtää kahta solmua kerrallaan.

Kun nopea osoitin saavuttaa pään, hidas osoitin on keskipisteessä. Tämä tekniikka toimii O (n) aikaa ilman lisätilaa.

5) Miten tunnistaisit syklin linkitetyssä listassa?

Syklin tunnistus on toinen klassinen ongelma. Vakioratkaisu käyttää Floydin kilpikonna- ja jänisalgoritmi:

  • Liikkua slow pointer yksi askel kerrallaan.
  • Liikkua fast pointer kaksi askelta kerrallaan.
  • Jos listassa on sykli, kaksi osoitinta kohtaavat.

Jos nopea osoitin saavuttaa null, listalla ei ole sykliä. Tämä metodi toimii O (n) aika ja O (1) tilaa.

6) Mitkä ovat linkitettyjen listojen edut ja haitat?

Linkitetyt listat tarjoavat useita etuja ja kompromisseja:

edut Haitat
Dynaaminen koko Ei satunnaista pääsyä
Helppo lisätä/poistaa Lisämuistia osoittimille
Tehokas kasvavalle datalle Huono välimuistin suorituskyky

Linkitetyt listat toimivat hyvin dynaamisen datan käsittelyssä, mutta voivat olla hitaampia kuin taulukot elementtien käytössä, koska jokainen käyttö vaatii läpikäynnin otsikosta.

AIHEESEEN LIITTYVÄT ARTIKKELIT

7) Miten yhdistät kaksi lajiteltua linkitettyä listaa?

Kahden lajitellun listan yhdistäminen on toinen yleinen haastatteluongelma. Ajatuksena on käydä molemmat listat läpi samanaikaisesti ja rakentaa uusi lajiteltu lista valitsemalla pienempi solmu kummastakin listasta jokaisessa vaiheessa.

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;
}

Tämä metodi säilyttää lajittelujärjestyksen ja toimii O(n + m) aika pituisille n ja m listoille.

8) Selitä, miten N:s solmu poistetaan linkitetyn listan lopusta.

Tehokkain tekniikka käyttää kaksi pistettä n solmun erottelu. Siirrä ensimmäistä osoitinta n askelta eteenpäin ja siirrä sitten molempia osoittimia, kunnes ensimmäinen saavuttaa pään. Toinen osoitin on tällöin juuri ennen kohdesolmua.

Tämä välttää listan pituuden laskemisen erikseen ja täydentää sen O (n) aika. Se käsittelee myös reunatapaukset, kuten ensimmäisen solmun poistamisen.

9) Mikä on aikavaativuus päästä käsiksi linkitetyn listan k:nteen elementtiin?

Pääsy kLinkitetyn listan . elementti vaatii läpikäymisen listan alusta loppuun. ksolmu. Koska linkitetyt listat eivät tarjoa suoraa indeksointia, tämä maksaa O (n) pahimmassa tapauksessa aikaa.

Sitä vastoin taulukot tukevat suoraa indeksointia O (1) ajan.

10) Miksi käyttäisit linkitettyä listaa taulukon sijaan?

Linkitetyt listat ovat erityisen hyödyllisiä, kun:

  • Odotat usein tapahtuvan lisäyksiä ja poistoja mielivaltaisissa kohdissa.
  • Et tiedä datasi kokoa etukäteen.
  • Muistin pirstoutuminen vaikeuttaa vierekkäisen muistin allokointia.

Ne tukevat tehokasta dynaamista muistin allokointia ja vakioaikaista lisäystä/poistoa listan lopussa tai tunnetulla solmuviittauksella – etuja, joita taulukot eivät voi verrata.

11) Mitkä ovat linkitettyjen listojen käytännön sovellukset?

Linkitettyjä listoja käytetään laajalti järjestelmissä, joissa dynaaminen muistin allokointi, usein lisättyjätai muuttuvan kokoiset tietorakenteet vaaditaan. Niitä toteutetaan useissa tietojenkäsittelytieteen keskeisissä käsitteissä ja sovelluksissa, kuten:

  • Dynaaminen muistinhallinta (käytetään käyttöjärjestelmissä)
  • Kumoa/Tee uudelleen -toiminnot tekstieditoreissa
  • Hajautustaulukon ketjutus törmäysten ratkaisemiseksi
  • Musiikki- tai videosoittolistan navigointi
  • Graafin vierekkäisyyden esitys
  • Polynomilaskennan

Nämä esimerkit havainnollistavat, kuinka linkitetyt listat tarjoavat joustavuutta ja tehokasta sekvenssien käsittelyä tilanteissa, joissa taulukon koon muuttaminen olisi kallista.

12) Selitä ero yksinkertaisesti ja kahdesti linkitettyjen listojen välillä.

Ominaisuus Yksittäin linkitetty luettelo Kaksoislinkitetty lista
Osoittimet 1 (vain seuraava solmu) 2 (edellinen ja seuraava)
traversal Vain yhteen suuntaan Molemmat suunteet
Muistin käyttö Less (vain yksi osoitin) Lisää (lisäosoitin)
poisto Vaikeampi (tarvitsee edellisen solmun) Helpompi
Käyttöesimerkki Pinon toteutus Selainhistorian navigointi

A kaksinkertaisesti linkitetty lista on monipuolisempi, mutta kuluttaa enemmän muistia. Sitä vastoin yksittäin linkitetyt luettelot ovat kevyitä ja tehokkaita yksisuuntaiseen liikkumiseen.

13) Miten poistat kaksoiskappaleet lajitellusta linkitetystä listasta?

Kun linkitetty lista on jo lajiteltu, kaksoiskappaleet ovat vierekkäin.

Käy lista läpi ja vertaa jokaisen solmun tietoja seuraavan solmun tietoihin. Jos ne täsmäävät, ohita seuraava solmu.

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;
        }
    }
}

Monimutkaisuus: O(n) aikaa ja O(1) avaruutta.

Lajittelemattomille listoille voidaan käyttää HashSet-metodia nähtyjen arvojen seuraamiseen.

14) Mitä eroa on lineaarisella ja ympyrälinkitettyllä listalla?

Ominaisuus Lineaarinen linkitetty lista Pyöreä linkitetty luettelo
Viimeinen solmu Viittaa NULL-arvoon Pisteet pääsolmuun
traversal Päättyy, kun next == NULL Jatkuva läpikulku
Käytä asiaa Pino, Jono Round robin -aikataulu
Monimutkaisuus yksinkertaisempi Monimutkaisempi käsittely

Ympyrälistat ovat erityisen hyödyllisiä sovelluksissa, kuten suorittimen ajoituksessa, jossa prosesseja suoritetaan syklisesti.

15) Miten kahden linkitetyn listan leikkauspiste löydetään?

Kahden yksinkertaisesti linkitettyjen listan leikkaamisen määrittäminen:

  1. Etsi molempien listojen pituudet.
  2. Siirrä pidemmän listan osoitinta pituuseron verran eteenpäin.
  3. Käy molemmat listat läpi samanaikaisesti, kunnes solmut ovat identtiset.

Vaihtoehtoisesti a HashSet voidaan käyttää vierailtujen solmujen tallentamiseen O(n) avaruuteen.

Tämä lähestymistapa on tehokas ja sitä kysytään usein ylemmän tason työhaastatteluissa.

16) Miten tarkistat, ovatko kaksi linkitettyä listaa identtisiä?

Kaksi linkitettyä listaa ovat identtisiä, jos:

  • Niillä on sama määrä solmuja.
  • Vastaavat solmun arvot ovat järjestyksessä identtiset.

algoritmi:

  1. Käy molemmat listat läpi yhdessä.
  2. Vertaa kunkin solmun tietoja.
  3. Jos kaikki parit täsmäävät ja molemmat saavuttavat NULL-arvon, ne ovat identtiset.

Ajan monimutkaisuus: O (n)

Avaruuden monimutkaisuus: O (1)

17) Mitä muistivuoto on linkitettyjen listojen yhteydessä?

A muistivuoto tapahtuu, kun dynaamisesti allokoituja solmuja ei vapauteta käytön jälkeen.

Linkitetyissä listoissa, jos delete or free() ei kutsuta listalta poistetuille solmuille, muisti pysyy varattuna, vaikka se ei olisi enää käytettävissä.

Esimerkiksi poistettujen solmujen vapauttamatta jättäminen C/-kielelläC++ johtaa muistin asteittaiseen loppumiseen, mikä puolestaan ​​hidastaa järjestelmää tai aiheuttaa kaatumisia.

Asianmukainen siivous käyttämällä destructoria tai eksplisiittistä deallokaatiota välttää tämän ongelman.

18) Selitä, miten pino toteutetaan linkitetyn listan avulla.

Jonkin sisällä pino, elementit noudattavat LIFO-järjestystä (viimeisenä sisään, ensimmäisenä ulos).

Linkitetty lista on ihanteellinen, koska lisäykset ja poistot tapahtuvat tehokkaasti listan alussa.

OperaTIONS:

  • Työntää: Lisää uusi solmu otsikkoon.
  • Pop: Irrota solmu päästä.
  • Kurkistaa: Palauta päätiedot.

edut:
Ei tarvitse kiinteän kokoista taulukkoa; kasvaa dynaamisesti elementtien siirtyessä järjestelmään.

19) Miten linkitettyä listaa voidaan käyttää jonon toteuttamiseen?

Jonkin sisällä jono, elementit noudattavat FIFO-järjestystä (ensimmäinen sisään, ensimmäinen ulos).

Käytä linkitettyä listaa, jossa:

  • Lisää jonoon (Lisää): Lisää solmu häntään.
  • Poista jonosta: Poista solmu otsikosta.

Tämä mahdollistaa molemmat toiminnot O (1) aika kahdella osoittimella — front ja rear.

Sitä käytetään yleisesti prosessien ajoituksessa ja tulostusjonojärjestelmissä.

20) Mitä eroja on taulukkoluettelolla ja linkitetyllä listalla? Java?

Aspect ArrayList LinkedList
varastointi Dynaaminen taulukko Kaksinkertaisesti linkitetty lista
Kirjautumisaika O (1) O (n)
Lisää/Poista Kallis keskellä Tehokas päissä
Ylimääräinen muisti Less Lisää (lisävinkkejä)
Käytä asiaa Usein käytetty Usein lisäys/poisto

Esimerkiksi: Käyttää ArrayList hakupainotteisia toimintoja varten ja LinkedList kun lisäys-/poistotoiminnot ovat hallitsevia.

21) Miten litistetään monitasoinen linkitetty lista?

A monitasoinen linkitetty lista voi sisältää solmuja, joilla on molemmat next ja child osoittimet (jokainen lapsi johtaa toiseen linkitettyyn listaan). Tavoitteena on litistää kaikki solmut yksitasoiseksi linkitettyksi listaksi.

Lähestyä:

  1. Käyttää pino or rekursiivinen funktio.
  2. Aloita pääsolmusta.
  3. Jos solmulla on child, työnnä sen next solmu pinoon ja tee child as next.
  4. Jatka, kunnes pino on tyhjä.

Ajan monimutkaisuus: O (n)

Avaruuden monimutkaisuus: O(n) rekursiolle/pinolle.

Esimerkki (käsitteellisesti):

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

Tämä kysymys arvioi ymmärrystäsi rekursiosta ja osoittimien manipuloinnista.

22) Miten kloonataan linkitetty lista satunnaisilla osoittimilla?

Jokaisella tämän erityisen linkitetyn listan solmulla on kaksi osoitinta:

  • next → osoittaa seuraavaan solmuun.
  • random → osoittaa mihin tahansa mielivaltaiseen solmuun.

Algoritmi (3 vaihetta):

  1. Lisää kloonattuja solmuja alkuperäisten solmujen väliin.
  2. Määritä klooneille satunnaisia ​​osoittimia (clone.random = original.random.next).
  3. Erota kaksi listaa toisistaan.

Tämä välttää ylimääräistä tilaa hajautusmapille ja toimii O (n) aikaa O (1) ylimääräistä tilaa.

Käyttötapa: Monimutkaisten tietorakenteiden (esim. graafien tai olioviittausten) syväkopiointi.

23) Mikä on ohituslista ja miten se liittyy linkitettyihin listoihin?

A ohituslista on kerroksellinen linkitetty listarakenne, joka mahdollistaa nopean haun, lisäyksen ja poiston (samanlainen kuin tasapainotetut puut).

OperaTUKSEN Keskimääräinen aika Pahimmassa tapauksessa
Haku O (log n) O (n)
Lisää/Poista O (log n) O (n)

Se sisältää useita tasoja, joissa ylemmät tasot "ohittavat" useita solmuja, mikä parantaa haun tehokkuutta.

Esimerkiksi: Käytetään tietokannoissa, kuten Redisissä, ja samanaikaisissa karttatoteutuksissa.

24) Miten palindromin voi havaita linkitetystä listasta?

Linkitetty lista on palindromi, jos se lukee samaa edestakaisin ja taaksepäin.

algoritmi:

  1. Etsi listan keskikohta.
  2. Revmuuten toinen puolisko.
  3. Vertaa kahta puoliskoa solmu solmulta.

Jos kaikki vastaavat solmut täsmäävät, kyseessä on palindromi.

Esimerkiksi:

1 → 2 → 3 → 2 → 1 → ✅ Palindromi

1 → 2 → 3 → 4 → ❌ Ei palindromi

Ajan monimutkaisuus: O (n)

Avaruuden monimutkaisuus: O (1)

25) Miten silmukka poistetaan linkitetystä listasta?

Jos silmukka on olemassa (käyttäen Floydin syklin tunnistusta), poista se seuraavasti:

  1. Havaitse hitaiden ja nopeiden osoittimien kohtaamispiste.
  2. Siirrä yksi osoitin päähän.
  3. Siirrä molempia osoittimia askel kerrallaan, kunnes ne kohtaavat silmukan aloitussolmu.
  4. Aseta edellisen solmun next että null.

Tämä lähestymistapa varmistaa, ettei syklien ratkaisemisessa käytetä ylimääräistä muistia.

26) Millä eri tavoilla linkitettyjä listoja voidaan esittää muistissa?

Linkitettyjä listoja voidaan esittää muodossa kolmella tavalla:

Edustustyyppi Tuotetiedot Käyttöesimerkki
Dynaamiset solmut Jokainen solmu allokoidaan ja linkitetään dynaamisesti C, C++
Staattinen taulukon esitys Käyttää taulukkoindeksejä osoittimien sijaan Sulautetut järjestelmät
Linkitetyt objektit Oliopohjainen esitys luokkien avulla Java, Python

Jokainen lähestymistapa sopii erilaisiin ympäristöihin – esimerkiksi taulukkopohjaisia ​​listoja käytetään, kun osoittimen käsittely on rajoitettua.

27) Miten löydät linkitetyn listan pituuden (iteratiivinen ja rekursiivinen)?

Iteratiivinen lähestymistapa:

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

Rekursiivinen lähestymistapa:

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

Molemmilla lähestymistavoilla on O (n) aikakompleksisuus; rekursio lisää O (n) puhelupinon aiheuttama tilan lisäys.

28) Selitä ympyrämäisten kaksinkertaisesti linkitettyjen listojen käsite esimerkin avulla.

Jonkin sisällä pyöreä kaksinkertaisesti linkitetty lista, jokaisella solmulla on kaksi linkkiä – yksi seuraavaan ja yksi edelliseen – ja viimeisen solmun next osoittaa päähän, kun taas pään prev osoittaa viimeiseen solmuun.

Esimerkkejä käyttötapauksista:

  • Reaaliaikaiset käyttöjärjestelmät (round-robin-ajoitus)
  • Musiikkisoittolistan jatkuva toisto
  • Navigointi välilehtien tai diojen välillä

edut:

  • Kaksisuuntainen läpikulku.
  • Ei null-viittauksia.
  • Tehokkaita lisäyksiä ja poistoja.

29) Miten poistat vaihtoehtoiset solmut linkitetystä listasta?

algoritmi:

  1. Aloita päästä.
  2. Poista joka toinen solmu muuttamalla osoittimia.
  3. Jatka, kunnes lista loppuu.

Esimerkiksi:

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

Monimutkaisuus:

  • Aika: O(n)
  • Välilyönti: O(1)

Tämä tarkistaa osoittimen läpikulun ja poistoturvallisuuden ymmärryksen.

30) Miten löydät linkitetyn listan n:nnen solmun alusta ja lopusta?

Alusta alkaen: Käydään listaa läpi, kunnes määrä = n.

Lopulta: Käytä kahta osoitinta.

  1. Siirrä ensimmäistä osoitinta n askelta eteenpäin.
  2. Liikuta molempia samanaikaisesti, kunnes ensimmäinen saavuttaa nollapisteen.
  3. Toinen osoitin osoittaa nyt n:teen solmuun lopusta.

Ajan monimutkaisuus: O (n)

Avaruuden monimutkaisuus: O (1)

Tämä lähestymistapa välttää pituuden erillisen laskemisen, mikä parantaa tehokkuutta.

31) Miten linkitettyä listaa järjestetään uudelleen?

Ongelma: Annettu lista L0 → L1 → … → Ln-1 → Ln, järjestele se uudelleen seuraavasti L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …

Vaiheet:

  1. Etsi listan keskikohta.
  2. Revmuuten toinen puolisko.
  3. Yhdistä kaksi puoliskoa vuorotellen.

Esimerkiksi:

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

Monimutkaisuus: Aika O(n), avaruus O(1).

Tämä testaa useita linkitetyn listan toimintoja yhdessä kysymyksessä.

32) Miten linkitetty lista osioidaan annetun arvon x ympärille?

Tavoite:
Järjestä solmut siten, että kaikki x:ää pienemmät solmut tulevat ennen x:ää suurempia tai yhtä suuria solmuja.

Lähestyä:

  • Ylläpidä kahta mallilistaa: before ja after.
  • Käy läpi alkuperäinen lista ja lisää solmut vastaaviin listoihin.
  • Yhdistä ne lopussa.

Esimerkiksi:

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

Tätä pyydetään usein datan uudelleenjärjestelykyvyn arvioimiseksi.

33) Miten linkitetty lista lajitellaan?

Koska linkitetyt listat eivät tue satunnaista käyttöä, Yhdistä lajittelu on paras valinta.

Vaiheet:

  1. Jaa lista puoliksi käyttämällä hitaita/nopeita osoittimia.
  2. Lajittele jokainen puolisko rekursiivisesti.
  3. Yhdistä lajitellut puolikkaat.

edut:

  • O(n log n) aika.
  • O(1) lisätilaa (iteratiivista versiota varten).

Toisin kuin taulukot, QuickSort on tehoton linkitettyjen listojen kanssa osoittimen uudelleenjärjestelyn monimutkaisuuden vuoksi.

34) Mitä eroa on yksinkertaisesti, kahdesti ja ympyränmuotoisilla linkitetyillä listoilla?

Ominaisuus Yksittäin kaksin verroin Pyöreä
Linkit Yksi (seuraava) Kaksi (edellinen ja seuraava) Viimeinen solmu yhdistyy päähän
traversal Vain eteenpäin Eteen- ja taaksepäin Ääretön läpikulku mahdollista
Lisäys/Poisto Kohtalainen Helpompaa molemmista päistä Erikoistapausten käsittely
Käytä asiaa Pino, Jono Kumoa toiminnot Round robin -aikataulu

Tämä vertailukysymys näyttää usein tarkistavan käsitteellistä selkeyttä.

35) Miten kahden ympyrämäisen linkitetyn listan leikkauspiste löytyy?

Tämä on leikkausongelman laajennus.

algoritmi:

  1. Tarkista, onko jokaisessa listassa silmukka.
  2. Jos molemmat ovat asyklisiä → käytä standardia leikkausalgoritmia.
  3. Jos molemmat ovat syklisiä → etsi kummallekin silmukan alku ja tarkista, ovatko ne samat tai yhdistetyt.

Tämä ongelma yhdistää syklin havaitseminen ja leikkauslogiikka, testaten monikäsitteistä päättelyä.

36) Selitä, miten solmu lisätään lajiteltuun linkitettyyn listaan.

Vaiheet:

  1. Luo uusi solmu annetulla arvolla.
  2. Liiku, kunnes löydät oikean asennon.
  3. Säätää next osoittimet vastaavasti.

Esimerkiksi:

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

Tämä on perusmanipulaatiotehtävä osoittimen säädön ymmärryksen testaamiseksi.

37) Miten jaat linkitetty listan kahteen osaan?

algoritmi:

  • Käytä hidasta ja nopeaa osoitinmenetelmää.
  • Kun fast saavuttaa lopun, slow tulee olemaan keskikohdassa.
  • Jaa tuossa solmussa.

Esimerkiksi:

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

Tämä operaatio on usein ensimmäinen vaihe linkitettyjen luetteloiden yhdistämislajittelussa.

38) Miten löydät arvon viimeisen esiintymän linkitetyssä listassa?

Käy läpi listaa pitäen silmällä viimeistä solmua, josta kohdearvo löytyy.

Pseudokoodi:

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

Monimutkaisuus: O (n)

Tämä tarkistaa lineaarisen läpikulun ja ehdontarkistuksen ymmärryksen.

39) Kuinka voit poistaa kaikki tietyn avaimen esiintymät linkitetystä listasta?

algoritmi:

  1. Käsittele pääsolmuja ensin, jos ne sisältävät kohdeavaimen.
  2. Sitten käydään läpi ja poistetaan seuraavat avaimen sisältävät solmut.

Esimerkiksi:

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

Monimutkaisuus: O (n)

Tämä osoittaa reunatapausten (erityisesti otsikon poiston) tuntemusta.

40) Mitkä ovat pinottujen ja linkitettyjen listarakenteiden keskeiset erot?

Ominaisuus Pinota Linkitetty luettelo
Käyttöoikeustyyppi LIFO (Last In, First Out) Peräkkäinen
Täytäntöönpano Taulukko tai linkitetty lista Solmupohjainen
OperaTIONS Työnnä/Ponnahda Lisää/Poista/Siirry
Joustavuus Rajoitettu pääsy Joustava käyttöoikeus
Käytä asiaa Funktiokutsujen hallinta Dynaaminen tiedonkäsittely

Pino voidaan toteuttaa käyttämällä linkitettyä listaa, mutta ne eroavat toisistaan ​​konseptiltaan – pinolla on rajoitettu pääsy, kun taas linkitetty lista on yleiskäyttöinen rakenne.

🔍 Haastattelukysymysten lista, jossa on linkitettyjä kysymyksiä tosielämän skenaarioilla ja strategisilla vastauksilla

1) Mikä on linkitetty lista ja miten se eroaa taulukosta?

Ehdokkaalta odotetaan: Haastattelija haluaa arvioida ymmärrystäsi perustietorakenteista ja kykyäsi vertailla kompromisseja.

Esimerkki vastauksesta: Linkitetty lista on lineaarinen tietorakenne, jossa elementit, joita kutsutaan solmuiksi, on yhdistetty osoittimilla. Jokainen solmu sisältää dataa ja viittauksen seuraavaan solmuun. Toisin kuin taulukot, linkitetyt listat eivät vaadi yhtenäistä muistia ja mahdollistavat dynaamisen koon muuttamisen, mutta niiden käyttöajat ovat hitaampia, koska elementtejä ei indeksoida.

2) Milloin valitsisit linkitetyn listan taulukon sijaan reaalimaailman sovelluksessa?

Ehdokkaalta odotetaan: He arvioivat käytännön harkintakykyäsi sopivien tietorakenteiden valinnassa.

Esimerkki vastauksesta: Valitsisin linkitetyn listan, kun tietoja on lisättävä ja poistettava usein, etenkin datajoukon keskellä. Edellisessä roolissani työskentelin tehtävien ajoitusominaisuuden parissa, jossa tehtäviä lisättiin ja poistettiin usein, ja linkitetty lista tarjosi paremman suorituskyvyn kuin taulukko.

3) Voitko selittää eron kerran linkitettyjen ja kahdesti linkitettyjen listojen välillä?

Ehdokkaalta odotetaan: Haastattelija haluaa varmistaa käsitteellisen selkeytesi ja kykysi selittää tekniset erot selkeästi.

Esimerkki vastauksesta: Yksinkertaisesti linkitetyssä listassa on solmuja, jotka osoittavat vain seuraavaan solmuun, kun taas kaksinkertaisesti linkitetyssä listassa on solmuja, jotka osoittavat sekä seuraavaan että edelliseen solmuun. Kaksinkertaisesti linkitetyt listat mahdollistavat helpomman taaksepäin kulkemisen, mutta vaativat enemmän muistia lisäosoittimen vuoksi.

4) Miten havaitset syklin linkitetyssä listassa?

Ehdokkaalta odotetaan: Tämä testaa ongelmanratkaisutaitojasi ja yleisten algoritmisten mallien tuntemustasi.

Esimerkki vastauksesta: Yleinen lähestymistapa on käyttää kahta eri nopeuksilla liikkuvaa osoitinta, mitä usein kutsutaan hitaan ja nopean osoittimen tekniikaksi. Jos osoitin on sykli, ne lopulta kohtaavat. Edellisessä työssä käytin tätä lähestymistapaa estääkseni äärettömiä silmukoita tietojenkäsittelyputkessa.

5) Mitä yleisiä toimintoja suoritetaan linkitetyille listoille?

Ehdokkaalta odotetaan: Haastattelija haluaa tietää, ymmärrätkö vakiotoiminnot ja niiden vaikutukset.

Esimerkki vastauksesta: Yleisiä operaatioita ovat lisäys, poisto, läpikäynti, haku ja listan peruutus. Jokaisella operaatiolla on erilainen ajallinen monimutkaisuus riippuen siitä, missä se suoritetaan, mikä on tärkeää tehokkaita järjestelmiä suunniteltaessa.

6) Miten solmun lisääminen linkitettyyn listaan ​​tehdään?

Ehdokkaalta odotetaan: He tarkistavat osoittimen manipuloinnin ymmärrystäsi ja yksityiskohtien huomioimista.

Esimerkki vastauksesta: Lisätäkseni solmun listan keskelle, käyn ensin läpi listan löytääkseni kohdesijainnin ja säädän sitten osoittimia niin, että uusi solmu osoittaa seuraavaan solmuun ja edellinen solmu uuteen solmuun. Osoitinten huolellinen päivittäminen on kriittistä listan rikkoutumisen välttämiseksi.

7) Kuvaile tilannetta, jossa linkitetty lista aiheutti suorituskykyongelmia, ja miten ratkaisit tilanteen.

Ehdokkaalta odotetaan: Tämä käyttäytymiskysymys arvioi kykyäsi reflektoida ja optimoida.

Esimerkki vastauksesta: Edellisessä työssäni käytettiin linkitettyä listaa usein tehtävissä hakuoperaatioissa, mikä johti hitaaseen suorituskykyyn. Tunnistin ongelman ja suosittelin siirtymistä tiivistepohjaiseen rakenteeseen, mikä parantaisi hakuaikoja merkittävästi.

8) Miten kääntäisit linkitetyn listan päinvastaiseksi?

Ehdokkaalta odotetaan: Haastattelija testaa loogista ajatteluasi ja ymmärrystäsi iteratiivisista tai rekursiivisista lähestymistavoista.

Esimerkki vastauksesta: Kääntäisin linkitetyn listan päinvastaiseksi iteroimalla sen läpi ja muuttamalla jokaisen solmun seuraavan osoittimen osoittamaan edelliseen solmuun. Tämä prosessi jatkuu, kunnes kaikki osoittimet on käännetty ja listan otsikko on päivitetty.

9) Mitkä ovat linkitettyjen listojen käytön edut ja haitat?

Ehdokkaalta odotetaan: He haluavat tasapainoisen näkökulman ja tietoisuuden kompromisseista.

Esimerkki vastauksesta: Etuja ovat dynaaminen koko sekä tehokkaat lisäykset ja poistot. Haittoja ovat suurempi muistin käyttö ja hitaammat hakuajat verrattuna taulukoihin. Edellisessä roolissani näiden kompromissien ymmärtäminen auttoi valitsemaan oikean rakenteen eri komponenteille.

10) Miten päätät, minkä tyyppistä linkitettyä listaa käytetään järjestelmäsuunnittelussa?

Ehdokkaalta odotetaan: Tämä tilannekysymys arvioi päätöksentekoa arkkitehtonisissa konteksteissa.

Esimerkki vastauksesta: Otan huomioon sellaiset tekijät kuin läpikulkutarpeet, muistirajoitukset ja operaatiotiheyden. Esimerkiksi jos vaaditaan taaksepäin kulkemista, kaksinkertaisesti linkitetty lista on sopivampi, kun taas yksinkertaisesti linkitetty lista riittää yksinkertaisempiin, muistia säästäviin toteutuksiin.

Tiivistä tämä viesti seuraavasti: