编译器不会推进单链表的递归反转

Question

我在一个类中有一个递归静态方法SinglyLinkedList，该方法由于不确定的原因而永远运行。这个类是通用的，它的声明如下：

public class SinglyLinkedList<E>{

这个类有一个内部泛型类Node，如下所示：

private static class Node<E> {

    private E element;

    private Node<E> next;

    public Node(E e, Node<E> n) {

        this.element = e;

        this.next = n;

    }

    public E getElement() {

        return this.element;

    }

    public Node<E> getNext() {

        return this.next;

    }

    public void setNext(Node<E> n) {

        this.next = n;

    }

}

此外，该类SinglyLinkedList还有以下字段：

private Node<E> head = null;

private Node<E> tail = null;

private int size = 0;

我遇到问题的方法被调用reverse，其目的是以递归方式反转单链表的顺序。这是此方法的代码：

public static SinglyLinkedList reverse(SinglyLinkedList l) {

    if (l.size < 2) return l;

    Node first = l.removeFirstNode();

    SinglyLinkedList reversed = reverse(l);

    reversed.addLast(first);

    return reversed;

}

该reverse方法使用一个非静态方法调用，removeFirstNode其目的是删除Node单链表中的第一个并返回它：

private Node<E> removeFirstNode() {

    if (isEmpty()) return null;

    //Node<E> answer = new Node<>(this.head.getElement(), null);

    Node<E> answer = this.head;

    this.head = this.head.getNext();

    this.size--;

    if (this.size == 0) this.tail = null;

    return answer;

}

该reverse方法还使用一个非静态方法调用，addLast其目的是将给定添加Node到单链表的末尾：

private void addLast(Node<E> n) {

    if (isEmpty()) this.head = n;

    else this.tail.setNext(n);

    this.tail = n;

    this.size++;

}

问题是，当我尝试在等于 2 的a上运行该reverse方法时，编译器到达该行SinglyLinkedListsize

reversed.addLast(first);

然后在addLast方法内部它停在线上

this.tail = n;

并永远运行而不终止。如果size等于 3 或更多，编译器将到达该行

reversed.addLast(first);

甚至没有进入方法就停在那里addLast。现在如果我更换线路

Node<E> answer = this.head;

与当前注释掉的行

Node<E> answer = new Node<>(this.head.getElement(), null);

该reverse方法将毫无问题地终止。有人能解释一下这是怎么回事吗？

编辑：我刚刚意识到 3 个或更多的不同行为size只是递归的产物。真正的问题在于当size等于 2 时该方法莫名其妙地终止于该行

this.tail = n;

Answer 1

的实现removeFirstNode()不会取消节点的下一个指针的链接。原始链表中，第一个节点的next指针指向第二个节点，第二个节点的next指针为空。在新链表中，第一个节点的 next 指针将指向第二个节点，但第二个节点的 next 指针将指向第一个节点（以前是第二个节点）。像这样的东西（原始列表）：+---+&nbsp; &nbsp; +---+| A |--->| B |--->null+---+&nbsp; &nbsp; +---+当重新排序时变成这样，因为 A 的下一个指针仍然指向 B：+---+&nbsp; &nbsp; +---+| B |--->| A |---++---+&nbsp; &nbsp; +---+&nbsp; &nbsp;|&nbsp; ^&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; |&nbsp; |&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; |&nbsp; +--------------+您可以将您的removeFirstNode()实现更改为如下所示：&nbsp; &nbsp; private Node<E> removeFirstNode() {&nbsp; &nbsp; &nbsp; &nbsp; if (isEmpty()) return null;&nbsp; &nbsp; &nbsp; &nbsp; Node<E> answer = this.head;&nbsp; &nbsp; &nbsp; &nbsp; this.head = this.head.getNext();&nbsp; &nbsp; &nbsp; &nbsp; answer.next = null; // Set next ptr to null&nbsp; &nbsp; &nbsp; &nbsp; this.size--;&nbsp; &nbsp; &nbsp; &nbsp; if (this.size == 0) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; this.tail = null;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; return answer;&nbsp; &nbsp; }该代码可能看起来像“停止”，因为调试器尝试使用 打印出列表toString()，我想它会遍历列表并且由于循环而永远不会完成。