Какой способ инвертирования связного списка выбрать: рекурсивный или итеративный

Что проверяют

Умеете ли вы оценивать не только время, но и память, и знаете ли, как рекурсия ведёт себя в JVM. Обычно просят написать оба варианта, а затем спрашивают, что будет со списком на миллион узлов.

Как отвечать

Сразу дайте рекомендацию: в рабочем коде итеративный, рекурсивный как упражнение или для заведомо коротких списков. Потом обоснуйте.

• итеративный: O(n) по времени и O(1) по памяти, три ссылки и один проход. Порядок присваиваний важен: сохранить next = head.next, развернуть head.next = prev, сдвинуть prev = head и head = next, в конце вернуть prev;
• рекурсивный: тоже O(n) по времени, но O(n) по памяти за счёт стека вызовов. Функция доходит до хвоста, а на обратном ходе делает head.next.next = head и head.next = null;
• стек в JVM: размер стека потока ограничен (-Xss, на 64-битных системах обычно порядка мегабайта), и на длинном списке рекурсия падает с StackOverflowError. Устранения хвостовых вызовов JVM не делает, поэтому даже хвостовой вариант с аккумулятором reverse(node, prev) стек не экономит.

Добавьте тестовые случаи: пустой список, один узел, два узла, длинный список. Если спросят про java.util.LinkedList, это двусвязный список, и там хватает Collections.reverse или descendingIterator(), узлы руками никто не переставляет.

Хорошо звучит и оговорка про читаемость: рекурсивная версия короче, её удобно показать как пример мышления «от хвоста», но в код ревью на прод её обычно попросят переписать.

Где спотыкаются

Забывают head.next = null в рекурсивной версии. Первые два узла начинают ссылаться друг на друга, и любой обход после этого зацикливается.

Говорят, что рекурсия «чище, значит лучше», не упоминая стек. Для Java это главный аргумент против неё, и интервьюер ждёт именно его.

Возвращают head вместо prev или теряют остаток списка, переприсвоив head.next до того, как сохранили следующий узел. Проговаривайте состояние трёх ссылок на каждом шаге, это ловит ошибку ещё до запуска.