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

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方法时，编译器到达该行SinglyLinkedListsizereversed.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 指针将指向第一个节点（以前是第二个节点）。

像这样的东西（原始列表）：

+---+    +---+

| A |--->| B |--->null

+---+    +---+

当重新排序时变成这样，因为 A 的下一个指针仍然指向 B：

+---+    +---+

| B |--->| A |---+

+---+    +---+   |

  ^              |

  |              |

  +--------------+

您可以将您的removeFirstNode()实现更改为如下所示：

    private Node<E> removeFirstNode() {

        if (isEmpty()) return null;

        Node<E> answer = this.head;

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

        answer.next = null; // Set next ptr to null

        this.size--;

        if (this.size == 0) {

            this.tail = null;

        }

        return answer;

    }

该代码可能看起来像“停止”，因为调试器尝试使用 打印出列表toString()，我想它会遍历列表并且由于循环而永远不会完成。