Напишите алгоритм инвертирования связного списка

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

Аккуратность в работе со ссылками и умение вслух проговорить инвариант цикла. Задача разминочная, поэтому смотрят не на факт решения, а на то, как вы разбираете граничные случаи и оцениваете сложность.

Как отвечать

Три ссылки, один проход, O(n) по времени и O(1) по памяти:

ListNode reverse(ListNode head) {
    ListNode prev = null;
    ListNode cur = head;
    while (cur != null) {
        ListNode next = cur.next;
        cur.next = prev;
        prev = cur;
        cur = next;
    }
    return prev;
}

Инвариант простой: всё, что левее cur, уже перевёрнуто, и prev это голова перевёрнутой части. Пустой список и список из одного узла проходят без отдельных веток, проверять их отдельно не нужно. Рекурсивный вариант короче, но занимает O(n) стека, а JVM не устраняет хвостовую рекурсию, поэтому на длинном списке он падает с StackOverflowError. Если спросят про стандартный LinkedList, скажите, что он двусвязный и там есть Collections.reverse, но от вас ждут ручной реализации на односвязном.

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

Теряют хвост: присваивают cur.next = prev до того, как сохранили cur.next во временную переменную. Остаток списка становится недостижимым, а цикл завершается на первом же узле.

Возвращают head. После разворота старая голова превращается в последний узел, у которого next равен null, и вызывающий код получает список из одного элемента. Возвращать нужно prev, потому что cur в этот момент уже null.

Обходят задачу через копирование: собирают значения в массив, переворачивают его и строят новый список. Работает, но это O(n) дополнительной памяти и не то, что просили. Ещё часто молчат про рекурсию и её цену, хотя вопрос про стек здесь задают почти всегда.