Чтобы развернуть связный список, я использую итеративный подход, который переставляет указатели узлов, чтобы изменить направление всех связей. Этот метод эффективен с временной сложностью O(n) и пространственной сложностью O(1).
Алгоритм поддерживает три указателя, которые проходят по списку и переворачивают связи:
ptr — отслеживает предыдущий узелnextptr — отслеживает текущий обрабатываемый узелtemp — сохраняет следующий узел перед изменением указателейtemplate void linklist::reverselist() {
nodeptr ptr = head;
nodeptr nextptr = ptr->_next;
while(nextptr) {
nodeptr temp = nextptr->_next;
nextptr->_next = ptr;
ptr = nextptr;
nextptr = temp;
}
head->_next = 0;
head = ptr;
}
ptr на текущий head и nextptr на следующий узелtemp перед изменением указателейnextptr->_next так, чтобы он указывал обратно на ptrptr и nextptrhead->_next в nullptr)Этот подход предпочтительнее рекурсивных решений в production-коде, так как не несёт риска переполнения стека на больших списках.
Итеративный алгоритм разворота связного списка использует три указателя для отслеживания предыдущего узла, текущего узла и следующего узла, требуя O(1) дополнительной памяти, так как никакие дополнительные структуры данных не создаются.
Новый — ещё не проверен сообществом
Вы