0

Как можно его развернуть, используя O(n) времени и O(1) памяти?

strunct Node {
    int payload;
    Node *next;
};
Node* head;
4

2 ответа 2

1

Вставка в начало списка O(1) по времени и по памяти. Поэтому можно сделать так: заведите новый пустой список, обходите старый, вставляя каждый элемент в начало нового. Итого получится как раз O(1) по памяти и O(n) по времени.

1

Без вставки в новый - просто идете по списку, разворачивая у каждого элемента поле next назад, на предыдущий. У бывшего самого первого поле next обнуляется, head устанавливается на бывший последний элемент.

По сути в общем-то, то же самое, что и вставка в новый..

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.