如果我们不知道初始状态，也不知道头/尾在哪里，我们如何计算双向链表（循环列表）内的元素呢？

Question

我正在做以下编程练习：火车中有多少辆货车？。声明是：

\n\n

\n

你坐在一列永久绕圈移动的火车上。火车\n是环形的：头与尾相连，你可以直接从一个\n转到另一个\n。

\n\n

每辆马车都有灯。灯的初始状态未知。如果您愿意，您可以打开或关闭它。

\n\n

数一下货车的数量！

\n\n

您可以根据需要在车厢之间移动。

\n\n

限制条件。清点车厢数量后，火车上的灯应处于初始状态。但最终你不需要在你开始的那辆马车里。

\n\n

使用已实现的 Train 方法：

\n\n

公共布尔 isLightOnInCurrentWagon()

\n\n

公共无效开关灯（）

\n\n

公共无效 goToNextWagon()

\n\n

公共无效 goToPreviousWagon()

\n\n

火车符号“1 : 0 : 0”表示您有一列有三节车厢的火车。第一辆货车的灯亮着，另外两辆货车的灯熄灭。

\n

\n\n

首先，我想保留三个整数列表：原始的、交换的和最终的。Original 会按开始时的状态存储灯光。切换将存储原始的补充（切换每辆货车的灯后）。Final 将使灯光保持原始状态（切换回原始状态后）。

\n\n

For example for train: 1:0:1\n\nOriginal: {1,0,1}\nSwitched: {0,1,0}\nFinal: {1,0,1}\n

\n\n

然而困难在于，我们如何知道火车的头/起点在哪里？

\n\n

此外，我尝试了一些基本情况的代码，其中火车只有一节车厢：

\n\n

import java.util.*;\npublic class Solution {\n    public int howManyWagons/*\xe2\x9d\x94*/(Train train){\n      int haveWeEnded = 0, prev = 0, first = 0, next = 0;\n      if(train.isLightOnInCurrentWagon()){\n        first = 1;\n      }\n      System.out.println("first: "+first);\n      train.switchLight();\n      train.goToNextWagon();\n      if(train.isLightOnInCurrentWagon()){\n        next = 1;\n      }\n      System.out.println("next: "+next);\n      train.switchLight();\n      train.goToPreviousWagon();\n      if(first != next){\n        train.switchLight();\n        train.goToPreviousWagon();\n        if(train.isLightOnInCurrentWagon()){\n          prev = 1;\n        }\n        System.out.println("prev: "+prev);\n        train.switchLight();\n      }\n      return prev == next && first != prev && first != next ? 1 : 0;\n    }\n}\n

\n\n

作为测试用例（取自挑战）：

\n\n

import org.junit.jupiter.api.Test;\n\nimport java.util.Random;\n\nimport static org.junit.jupiter.api.Assertions.*;\n\nclass SolutionTest extends Train {\n\n    Solution sol = new Solution();\n    Random rand = new Random();\n\n    @Test\n    void howManyWagonsCornerCases() {\n\n        String repr;\n        Train train;\n\n        repr = "1";\n        train = Train.fromRepr(repr);\n        assertEquals(1, sol.howManyWagons(train), repr);\n\n        repr = "1 : 0 : 1 : 0 : 0";\n        train = Train.fromRepr(repr);\n        assertEquals(5, sol.howManyWagons(train), repr);\n\n        repr = "1 : 0 : 0";\n        train = Train.fromRepr(repr);\n        assertEquals(3, sol.howManyWagons(train), repr);\n\n        repr = "1 : 1 : 0 : 0 : 1 : 1";\n        train = Train.fromRepr(repr);\n        assertEquals(6, sol.howManyWagons(train), repr);\n\n        repr = "0 : 0 : 0 : 0 : 0";\n        train = Train.fromRepr(repr);\n        assertEquals(5, sol.howManyWagons(train), repr);\n\n        repr = "1 : 1 : 1 : 1 : 1";\n        train = Train.fromRepr(repr);\n        assertEquals(5, sol.howManyWagons(train), repr);\n\n\n        repr = "1 : 0 : 1 : 0 : 0 : 1 : 1 : 0 : 0";\n        train = Train.fromRepr(repr);\n        assertEquals(9, sol.howManyWagons(train), repr);\n    }\n\n\n}\n

\n\n

所以当只有一辆马车时，它确实算数。但是我们怎样才能使这个通用呢？因为如果我们有 5 辆货车（第二次测试），如：“1 : 0 : 1 : 0 : 0”，代码输出：

\n\n

first: 1\nnext: 0\nprev: 0\n

\n\n

因为它检测到的模式与只有一辆马车一样，所以它返回 1 而不是 5。

\n\n

另外，我读过：

\n\n

\n
• 求双向链表的长度
\n
• 循环链表 - 计算节点数
\n
• https://www.geeksforgeeks.org/count-nodes-circular-linked-list/
\n
• 计算链表中可能循环的节点数
\n

\n\n

我们如何计算双向链表（循环链表）中的元素，我们不知道初始状态，也不知道 head / tail\xe2\x80\xbd 在哪里

\n\n

编辑：使用@Chamika的答案我试图解释创建算法的思维过程是如何的

\n\n

import java.util.*;\n\npublic class Solution {\n  public int howManyWagons/*\xe2\x9d\x94*/(Train train){\n    boolean end = false;\n    int count = 1;\n    while(!end){\n      // We save the light of the initial wagon to be able to reset it later\n      boolean isFirstWagonLightOn = train.isLightOnInCurrentWagon();\n      //\xef\xb8\x8f We turn off the light of the initial wagon, to mark \xe2\x9b\xb3 where we started this iteration\n      if(train.isLightOnInCurrentWagon()){\n        train.switchLight();\n      }\n      goForward(train,count);\n      //If the light is on , we know we are not in the initial wagon, we go to the initial wagon and count it\n      if(train.isLightOnInCurrentWagon()){\n        goBack(train,count);\n        count++;\n      //When the light is off \xef\xb8\x8f, we may have go back to the initial position\n      }else{\n        //We switch the light ,go back\n        train.switchLight();\n        goBack(train,count);\n        //If after going back the wagon light is on , it means we stand inside the end wagon\n        if(train.isLightOnInCurrentWagon()){\n          end=true;\n        }else{\n          //If light is off \xef\xb8\x8f, we have not been in the end position yet\n          goForward(train,count);\n          train.switchLight();\n          goBack(train,count);\n          count++;\n        }\n      }\n      //Reset end position light\n      if(isFirstWagonLightOn != train.isLightOnInCurrentWagon()){\n        train.switchLight();\n      }\n    }\n  return count;\n  }\n\n  public static void goForward(Train train,int count){\n    while(count > 0){\n      train.goToNextWagon();\n      count--;\n    }\n  }\n  public static void goBack(Train train,int count){\n    while(count > 0){\n      train.goToPreviousWagon();\n      count--;\n    }\n  }\n}\n

\n

Answer 1

记录当前车厢内灯光的状态。candidateWagonCount然后在从 1 到无穷大（或 到）的循环中查看火车上Integer.MAX_VALUE是否有车厢。candidateWagonCount该检查按如下方式进行：

\n

\n
1. 把灯关掉。
\n
2. 推动candidateWagonCount货车前进。如果灯亮了，我们就知道candidateWagonCount火车上不能有车厢。返回candidateWagonCount到原来的位置并进入下一个迭代。
\n
3. 如果灯灭了，我们可能又回到了起点。现在将candidateWagonCount货车移回我们知道的起点。将灯打开。再次推动candidateWagonCount货车前进。如果灯现在亮了，我们就知道我们已经回到了起点。candidateWagonCount因此，火车上一定有车厢。将灯设置为原始状态（打开或关闭）并退出。否则将candidateWagonCount货车移回起始位置。
\n

\n

在我看来，困难在于不知道起点或终点在哪里，因为火车是圆形的，所以没有\xe2\x80\x99t。您也可以决定考虑火车出发的位置。

\n

对我来说，挑战在于我们如何知道什么时候已经绕了一整圈。如果我们只是沿着火车的一个方向移动，即使我们认出了我们之前离开的一种灯光模式，我们也不知道我们是否回来了，或者我们来到了一系列新的车厢，恰好有相同的模式。解决方案是在将某个灯关闭和打开后都采取相同的步骤。

\n