创建反向链接列表

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;
}

作为结果，我们返回链表的新标题。