algorithm - 创建反向链表

Question

Java 代码: /image/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，我们只需要让第二个指针以第一个为next，并将第二个的next设置为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;
}

我们返回链表的新头部作为结果。