Java链表问题

Question

我有两个练习问题，我很难理解。对于#1，答案是列表是反向打印的，有人能向我解释一下吗？还有#7，为什么列表一旦达到null就开始倒退？如果有人能提供一些快速的解释，我们将不胜感激，谢谢！

1( 如果我们用头节点调用给定的链表，下面的函数对它做什么

void method1(Node<T> node) {
  if(node == null)
    return;
  method1(node.getNext());
  System.out.println(node.getData().toString());
}

a。打印链接列表的节点。

b。按相反顺序打印链接列表的节点。

c。打印链接列表的备用节点。

d。按相反顺序打印备用节点。

回答

b。按相反顺序打印链接列表的节点。

7( 如果我们用链表1的headnode调用它，这个方法将打印什么→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

回答

c。1 3 5 5 3 1

Answer 1

问题1:

这是一个递归方法调用，意味着它不断地调用自己，直到满足break条件(在这种情况下，没有下一个节点可以移动到(。所以，让我们一行一行地走一遍。

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，但在其他每个节点上，这意味着每次调用节点时都会跳过它。

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

Answer 2

如果绘制调用堆栈，它们都更容易可视化。这些指令是按顺序执行的，所以我发现可视化调用序列和调用堆栈深度很有帮助，如下所示：

问题1:

List = 1 → 2 → 3 → 4 → 5 → 6
method1(1)
  method1(2)
    method1(3)
      method1(4)
        method1(5)
          method1(6)
            method(null)
              return
            println(6)
          println(5)
        println(4)
      println(3)
    println(2)
  println(1)

这里的呼叫顺序可以从上到下看到。在打印任何内容之前调用method1。一旦method1达到基本情况，它将返回到上一次调用，在本例中为method1(6)调用。

这里的每个缩进都是另一个递归调用，有助于可视化调用堆栈。有很多非常好的答案可以比我更好地解释递归(比如程序员.stackeexchange.com上的这个(

问题7：

你可以对这个问题做同样的事情：

1 → 2 → 3 → 4 → 5 → 6
method1(1)
  printf("%f ", 1)
  method1(3) // node.getNext().getNext() = 1 → 2 → 3
    printf("%f ", 3)
    method1(5)
      printf("%f ", 5)
      method1(null) // node.getNext().getNext() = 5 → 6
        return
      printf("%f ", 5)
    printf("%f ", 3)
  printf("%f ", 1)