LinkedList 不打印特殊情况下的第一个元素

Question

我是递归概念的新手，在练习时遇到了一个无法获得逻辑推理的问题。 对于下面的代码片段，链接的第一个元素没有被打印出来(假设列表有多个元素(。

public void foo(ListNode head) {
foo1(head, head.next);
}
private void foo1(ListNode curr, ListNode nextNode) {
if (nextNode == null) {
return;
}
curr = nextNode;
nextNode = curr.next;
foo1(curr, nextNode);
System.out.println(curr);
}

例如，如果列表有 3 个元素作为 1 -> 2 -> 3 -> null，则只打印 3 和 2。 Foo 方法对 head 元素进行了调用，这是一个，所以它不应该在输出中打印 1 个。 请帮助我了解我在这里做错了什么。

Answer 1

curr = nextNode;
...
System.out.println(curr);

问题是您在打印之前将 curr 设置为其后续版本。

private void foo1(ListNode curr) {
if (curr == null)
return;
System.out.println(curr);
foo1(curr.next);
}

Answer 2

原因

原因是，在打印第一个元素之前，代码会将值从第一个元素更改为第二个元素。您的代码中还存在另一个问题，当我们传递一个元素时，它也不会打印该元素。因为考虑到这一点，您有一个节点 5，下一个节点为 null。当您将此节点传递给foo1()方法时，它会立即达到条件nextNode为 null 并返回，这里没有机会打印第一个节点 5。

我修改了您的相同代码以按预期完美运行，请看下文。

public void foo(ListNode head) {
foo1(head, head.next);
}
private void foo1(ListNode curr, ListNode nextNode) {
if(curr != null)
System.out.println(curr);
if (nextNode == null) {
return;
}
curr = nextNode;
nextNode = curr.next;
foo1(curr, nextNode);
}