递归打印循环链表

Question

在我的一个教程中，我被这个问题难住了：

给定一个只有一个尾指针的循环链表，使用以下标头编写一个递归方法，从第一个元素开始递归打印出列表：

公共无效循环打印（）

如果没有说明从第一个元素开始打印列表，我可以很容易地做这个问题。但是由于这个问题强制执行的多种限制，我感到困惑。有人可以建议我如何解决这个问题吗？

谢谢。

Answer 1

如果是循环链表，这意味着最后一个元素（尾巴）有一个指向第一个元素的字段。所以此时此刻你也有头（可以这么说）。

例如，您可以通过以下方式执行此操作：

1. 打印尾巴的next元素（即第一个元素）。
2. 将第二个元素分配给尾巴的下一个元素。
3. 重复。

Answer 2

列表只有一个圆圈，就像一个循环缓冲区吗？然后，您可以打印，直到下一个指针与对列表的引用相同。

如果圆圈可以进入任何先前的元素，那么您需要应用一种 Turtoise 和 hare 算法。

使用单链表很容易。如果您有像 Scheme cons 单元格，可以在两个指针中都有结构，这需要相当多的回溯和内务管理，那就不那么容易了。

至于方法签名的问题，我还没有听说过 Java 中的内部方法，所以你需要定义一个助手。

public void circularPrint()
{
  circularPrintAux(this);
}

对于土豆和野兔来说，这将是：

public void circularPrint()
{
  if( this.next == this )
      ...
  else
      circularPrintAux(this, this.next);
}

Answer 3

您需要传入两个参数，当前元素和起始元素。对于您的第一次通话，这些将是相同的。打印当前元素后，递归调用列表中的下一个元素。仅当下一个元素 ！= 起始元素时，才执行递归调用。