Как можно его развернуть, используя O(n) времени и O(1) памяти?
strunct Node {
int payload;
Node *next;
};
Node* head;
Stack Overflow на русском — это сайт вопросов и ответов для программистов. Присоединяйтесь! Регистрация займёт не больше минуты.
Присоединиться к сообществуКак можно его развернуть, используя O(n) времени и O(1) памяти?
strunct Node {
int payload;
Node *next;
};
Node* head;
Вставка в начало списка O(1) по времени и по памяти. Поэтому можно сделать так: заведите новый пустой список, обходите старый, вставляя каждый элемент в начало нового. Итого получится как раз O(1) по памяти и O(n) по времени.
Без вставки в новый - просто идете по списку, разворачивая у каждого элемента поле next
назад, на предыдущий. У бывшего самого первого поле next
обнуляется, head
устанавливается на бывший последний элемент.
По сути в общем-то, то же самое, что и вставка в новый..