Получение списка в обратном порядке

Условие

Дан односвязный список, каждый узел которого хранит некоторое целое значение и ссылку на следующий элемент. Требуется написать функцию, которая формирует и возвращает новый список, где элементы расположены в обратном порядке относительно исходного.

class Node {
    Node next;
    int value;
}

public Node reverse(Node root) {
    return null;
}

Ответ

Проходите исходный список и добавляйте копию каждого узла в начало нового. Это развернёт порядок, не меняя next у исходных узлов.

public Node reverse(Node root) {
    Node reversed = null;
    for (Node current = root; current != null; current = current.next) {
        Node copy = new Node();
        copy.value = current.value;
        copy.next = reversed;
        reversed = copy;
    }
    return reversed;
}

Для null результат null. Время O(n), память O(n) на новые узлы; дополнительный стек не нужен. Предполагается ацикличный список. Разворот ссылок на месте дал бы O(1) дополнительной памяти, но нарушил бы требование сформировать новый список.