Развернуть односвязный список

72. Развернуть односвязный список

Условие задачи:
Дан односвязный список:

1 → 2 → 3 → 4 → null

Необходимо изменить направление ссылок между узлами и получить список:

4 → 3 → 2 → 1 → null

Код:

public class Main {

    public static void main(String[] args) {
        OneList four = new OneList(4, null);
        OneList three = new OneList(3, four);
        OneList two = new OneList(2, three);
        OneList one = new OneList(1, two);

        System.out.println(one.x);
        System.out.println(one.next.x);
        System.out.println(one.next.next.x);
        System.out.println(one.next.next.next.x);
    }

    public static class OneList {

        OneList next;
        int x;

        OneList(int x, OneList next) {
            this.x = x;
            this.next = next;
        }
    }
}

Спойлеры к решению

Подсказки

💡 Храни ссылки на предыдущий, текущий и следующий узлы.
💡 Сохрани следующий узел до изменения current.next.
💡 На каждой итерации направляй current.next на предыдущий узел.
💡 После завершения цикла previous станет новой головой списка.

Решение

public class Main {

    public static void main(String[] args) {
        OneList four = new OneList(4, null);
        OneList three = new OneList(3, four);
        OneList two = new OneList(2, three);
        OneList one = new OneList(1, two);

        OneList head = reverse(one);
        OneList current = head;

        while (current != null) {
            System.out.println(current.x);
            current = current.next;
        }
    }

    public static OneList reverse(OneList head) {
        OneList previous = null;
        OneList current = head;

        while (current != null) {
            OneList next = current.next;

            current.next = previous;
            previous = current;
            current = next;
        }

        return previous;
    }

    public static class OneList {

        OneList next;
        int x;

        OneList(int x, OneList next) {
            this.x = x;
            this.next = next;
        }
    }
}

На каждой итерации сначала сохраняется ссылка на оставшуюся часть списка:

OneList next = current.next;

Затем ссылка текущего узла разворачивается:

current.next = previous;

После завершения цикла переменная previous содержит новую голову списка.

Результат:

Временная сложность — O(n), дополнительная память — O(1).