Алгоритми та структури даних · Middle · Запитання 26 з 75
Як розвернути однозв'язний список ітеративно?
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; - ✓Правильна відповідь:
cur.next = prev; prev = cur; cur = next;
Пояснення
Вказівник кожного вузла перенаправляється на попередній вузол, після чого обидва вказівники рухаються вперед. next зберігають заздалегідь, інакше решта списку загубиться. O(n) часу, O(1) пам'яті.