Algoritmus a k-es elem egyszerűen összekapcsolt listáján való kereséshez a végén

Ez az algoritmus rekurzívan és nem rekurzívan valósítható meg. A rekurzív megoldások általában érthetőbbek, de kevésbé optimálisak. Például a probléma rekurzív végrehajtása majdnem fele rövidebb, mint a nem recursív, de O (n) szóközöket foglal el, ahol n az összekapcsolt listában szereplő elemek száma.

A probléma megoldásakor ne feledje, hogy kiválaszthatja a k értékét, így k = 1 átvitelkor kapjuk az utolsó elemet, 2 - az utolsó előtti, stb. Vagy válaszd ki, hogy k = 0 megfelel az utolsó elemnek.

Megoldás 1. A kapcsolt lista mérete ismert

Ha ismeretes a csatolt lista mérete, akkor a végén a k-es elem könnyen kiszámítható (hossza - k). Át kell menned a listán, és meg kell találnod ezt az elemet.

2. megoldás Rekurzív megoldás

Az ilyen algoritmus rekurzívan átadja a csatlakoztatott listát. Amikor elérte az utolsó elemet, az algoritmus elkezd számlálni és a számláló nullázódik. Minden lépés lépésenként növeli a számlálót. Amikor a számláló eléri a k ​​értéket, akkor a keresett elem megtalálható.

Ennek az algoritmusnak a végrehajtása rövid és egyszerű - elegendő az egész értéket a veremen keresztül átengedni. Sajnos a visszatérési utasítás nem tudja visszaadni a csomópont értékét. Szóval hogyan tudod ezt a nehézséget megoldani?

A megközelítés: ne tegyen vissza egy tételt

Nem tudsz visszaadni egy elemet, azonnal kinyomtatod, amint megtalálod. És a visszatérési nyilatkozatban adja vissza a számláló értékét.

A megoldás igaz, de a másik irányba megy.

B megközelítés: C ++ használata

A második módszer a C ++ használata, és az érték referenciaként való átadása. Ez a megközelítés nemcsak visszaadja a csomópont értékét, hanem a számláló frissítését a mutató hozzáadásával.

3. megoldás. Iteratív megoldás

Az iteratív megoldás bonyolultabb, de optimálisabb is. Két mutatót használhat - p1 és p2. Először is mindkét mutató a lista tetejére mutat. Ezután mozgassa a p2-t a k csomópontok előtt. Most mindkét mutatót egyszerre mozgatjuk. Amikor a p2 eléri a lista végét, a p1 a kívánt elemre mutat.