Algorytmy i struktury danych · Middle · Pytanie 26 z 75
Jak iteracyjnie odwrócić listę jednokierunkową?
let prev = null, cur = head;
while (cur) {
const next = cur.next;
// ?
}
return prev;- 1
cur = cur.next; prev.next = cur; next = prev; - 2
prev = cur.next; cur.next = null; cur = prev; - ✓Poprawna odpowiedź:
cur.next = prev; prev = cur; cur = next;
Wyjaśnienie
Wskaźnik każdego węzła jest odwracany na poprzedni węzeł, a potem oba wskaźniki idą do przodu. next zapisuje się najpierw, inaczej reszta listy by przepadła. O(n) czasu, O(1) pamięci.