Я реализую собственный односвязный список на Java для проекта, и мне нужно реализовать метод для изменения списка. Основное ограничение заключается в том, что это должно быть сделано
на месте (пространственная сложность O(1)), то есть мне следует манипулировать только указателями существующих узлов.
Мой текущий подход: я пытаюсь использовать три указателя (
, current и next), но у меня возникли проблемы с правильным переназначением заголовка и хвоста в конце процесса, чтобы избежать потери ссылок.
Минимальный воспроизводимый пример:
Код: Выделить всё
public void reverseInPlace() {
Node prev = null;
Node current = head;
Node next = null;
tail = head; // The original head becomes the new tail
while (current != null) {
next = current.getNext();
current.setNext(prev);
prev = current;
current = next;
}
head = prev;
}
Хотя логика работает для списков с тремя и более узлами, меня беспокоят пограничные случаи. Это стандартный способ обработки нулевых указателей для пустых списков или списков с одним узлом в Java? Существуют ли потенциальные утечки памяти при таком переназначении указателя?
