Acest algoritm poate fi implementat recursiv și nerecursiv. Soluțiile recursive sunt de obicei mai ușor de înțeles, dar mai puțin optime. De exemplu, implementarea recursivă a acestei probleme este aproape pe jumătate mai scurtă decât nerecursivă, dar ocupă spații O (n), unde n este numărul de elemente din lista conectată.
Când rezolvăm această problemă, rețineți că puteți selecta valoarea lui k astfel încât atunci când transferăm k = 1, obținem ultimul element, 2 - cel penultim, etc. Sau alegeți k astfel încât k = 0 să corespundă ultimului element.
Soluție 1. Este cunoscută dimensiunea listei legate
Dacă dimensiunea listei legate este cunoscută, elementul k de la capăt este ușor de calculat (lungime - k). Trebuie să treceți prin listă și să găsiți acest element.
Soluția 2. O soluție recursivă
Un astfel de algoritm trece în mod recursiv lista conectată. La atingerea ultimului element, algoritmul începe numărarea în jos și contorul este resetat la 0. Fiecare pas mărește contorul cu 1. Când contorul ajunge la k, elementul căutat va fi găsit.
Implementarea acestui algoritm este scurtă și simplă - este suficient să treci întreaga valoare prin stivă. Din păcate, declarația de returnare nu poate returna valoarea nodului. Deci, cum te simți în jurul acestei dificultăți?
Abordarea A: nu returnați un element
Nu puteți returna un element, ci doar să-l imprimați imediat, imediat ce este găsit. Și în declarația de returnare, returnați valoarea contorului.
Soluția este adevărată, dar puteți merge invers.
Abordarea B: folosiți C ++
A doua modalitate este de a folosi C ++ și de a transmite valoarea prin referință. Această abordare permite nu numai returnarea valorii nodului, ci și actualizarea contorului prin transmiterea unui indicator la acesta.
Soluția 3. O soluție iterativă
Soluția iterativă va fi mai complicată, dar și mai optimă. Puteți utiliza două indicii - p1 și p2. Mai întâi, ambii indicatori indică partea de sus a listei. Apoi mutați p2 în nodurile k în față. Acum începem să mișcăm simultan ambii indicatori. Când p2 ajunge la sfârșitul listei, p1 va indica elementul de care avem nevoie.
Trimiteți-le prietenilor: