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

Question

Java-код: https://i.stack.imgur.com/6pBfp.png Я пытаюсь перевернуть Связанный список, но получаю ошибку StackOverFlow и не могу понять, почему...

Я был бы рад, если бы кто-нибудь мог помочь мне здесь

public static void reverseLinkedList(IntNode head) {
    IntNode current = head;
    IntNode next = current.getNext();

    while (next != null) {
        IntNode temp = current;
        current = next;
        next = next.getNext();
        current.setNext(temp);
    }
    System.out.println(current);
}


Exception in thread "main" java.lang.StackOverflowError
    at java.base/java.lang.AbstractStringBuilder.append(AbstractStringBuilder.java:538)
    at java.base/java.lang.StringBuilder.append(StringBuilder.java:174)
    at java.base/java.lang.StringBuilder.<init>(StringBuilder.java:125)
    at IntNode.toString(IntNode.java:31)
    at java.base/java.lang.String.valueOf(String.java:2951)
    at java.base/java.lang.StringBuilder.append(StringBuilder.java:168)
    at IntNode.toString(IntNode.java:31)
    at java.base/java.lang.String.valueOf(String.java:2951)

Answer 1

Сама ошибка stackoverflow отсутствует в списке reverseLinked.Это ToString, которая вызовет эту ошибку.Но это вызвано тем, что ваш обратный связанный список создает бесконечный цикл: два узла, которые указывают друг на друга.

Вы должны каждый раз иметь ссылку на три последовательных узла.Итак:

… ← B   C → D → E → …
    ↑   ↑   ↑

Мы можем каждый раз позволить C указывать на B как следующий узел:

… ← B ← C   D → E → …
    ↑   ↑   ↑

, а затем переходить к следующему элементу:

… ← B ← C   D → E → …
        ↑   ↑   ↑

Если третий указатель равен null, нам нужно только позволить второму указателю взять первый в качестве следующего и установить следующий из второго на null:

… ← Y   Z → null
    ↑   ↑   ↑

Таким образом, мы конвертируем это в:

… ← Y ← Z   null
    ↑   ↑   ↑

Таким образом, мы можем реализовать это в алгоритме следующим образом:

public static IntNode reverseLinkedList(IntNode node0) {
    if(node0 == null) {
        return null;
    }
    IntNode node1 = node0.getNext();
    node0.setNext(null);
    if(node1 == null) {
        return node0;
    }
    Int node2 = node1.getNext();
    node1.setNext(node0);
    while(node2 != null) {
        node1.setNext(node0);
        node0 = node1;
        node1 = node2;
        node2 = node2.getNext();
    }
    node1.setNext(node0);
    return node1;
}

В результате мы возвращаем новый заголовок связанного списка.