java - 递归打印循环链表

Question

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

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

公共无效循环打印（）

如果没有说明从第一个元素开始打印列表，我可以轻松地完成这个问题。但是由于这个问题实施的多重限制，我感到很困惑。有人可以告诉我如何解决这个问题吗？

谢谢你。

Answer 1

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

如果圆圈可以位于任何先前的元素中，那么您需要应用Turtoise and hare 算法之一。

使用单链表很容易。如果你有类似的 Schemecons单元格，它可以在两个指针中都有结构，这将需要相当多的回溯和内务处理，那就不那么容易了。

至于您的方法签名问题，我没有听说过 Java 中的内部方法，因此您需要定义一个助手。例如。

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

对于 turoise 和 hare，它将是：

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

Answer 2

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

例如，您可以这样做：

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

Answer 3

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