Java 链表问题

Question

我有两个练习题无法理解。对于#1，答案是列表是反向打印的，有人可以向我解释一下吗？另外#7，为什么列表一旦到达空值就开始向后移动？如果有人可以提供一些快速解释，我们将不胜感激，谢谢!

1) 如果我们使用头节点调用以下函数，它会对给定的链表执行什么操作？

void method1(Node<T> node) {
  if(node == null)
    return;

  method1(node.getNext());
  System.out.println(node.getData().toString());
}

a. Prints the nodes of the linked list.

b. Prints the nodes of the linked list in reverse order.

c. Prints alternate nodes of the linked list.

d. Prints alternate nodes in reverse order.

Answer

b. Prints the nodes of the linked list in reverse order.

7) 如果我们用链表 1 → 2 → 3 → 4 → 5 → 6 的头节点调用这个方法，它会打印什么？

void method1(Node<Integer> node) {
  if (node == null)
    return;
  System.out.printf(“%d ”, node.getData());

  if (node.getNext() != null)
    method1(node.getNext().getNext());
  System.out.printf(“%d ”, node.getData());
}

a. 1 6 2 5 3 4

b. 1 3 5 6 4 2

c. 1 3 5 1 3 5

d. 1 3 5 5 3 1

Answer

c. 1 3 5 5 3 1

Answer 1

问题1:

这是一个递归方法调用，意味着它不断调用自身，直到满足中断条件(在这种情况下，没有要移动到的下一个节点)。那么，让我们逐行讨论一下。

void method1(Node<T> node) {
    if(node == null) // ends the recursive calls without doing anything extra
        return;

    method1(node.getNext()); // Do something with the next node before this node
    System.out.println(node.getData().toString()); // Print contents of current node.
}

如您所见，我们第一次实际打印任何内容是在到达链表末尾时(当 node.next() 返回 null 时)。在第一次打印之后，调用在堆栈中向上移动(因此在列表中向后移动)，同时打印每个节点的内容。

问题2:

这与问题 1 几乎相同，只是有一些变化。首先，我们在递归调用之前和之后打印当前节点的内容。因此，实际上，我们将按顺序打印每个节点的内容，然后按相反的顺序打印。稍微令人困惑的部分是，我们在每个节点上调用 method1 ，但在每个其他节点上调用，这意味着每次调用时我们都会跳过一个节点。

因此，总结这个问题的答案，我们有效地打印当前节点的内容，跳过一个节点，打印下一个节点的内容，等等......直到我们到达可用节点的末尾，然后我们只是回溯并再次打印所有内容(只是这次以相反的顺序)。