我们如何计算双链表(循环列表)中的元素，因为我们不知道初始状态，也不知道头/尾在哪里

Question

我正在进行以下编程练习：列车上有多少辆货车？。声明是：

你乘坐的是一列永远在圆周上行驶的火车。列车是环状的：头部和尾部相连，你可以从那里开始直接对另一个人。

每辆马车都有一盏灯。灯的初始状态不是已知。如果你愿意，你可以打开或关闭它。

数一下货车的数量！

你可以随心所欲地在车厢之间移动。

禁忌。数完货车后，火车上的灯应该处于初始状态。但最终你不需要在和你出发的马车一样。

使用实施的列车方法：

公共布尔值isLightOnInCurrentWagon()

public void switchLight()

public void goToNextWagon()

public void goToPreviousWagon()

火车符号"1:0:0"表示你有一列三人的火车马车第一辆货车的灯亮着，另外两辆车的灯熄灭了。

首先我想保留三个整数列表，原始、切换和最终。Original会像一开始一样储存灯光。Switched将存储原始的补码(在切换每辆马车的灯后)。Final将使灯光保持原始状态(切换回原始状态后)。

For example for train: 1:0:1
Original: {1,0,1}
Switched: {0,1,0}
Final: {1,0,1}

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

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

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

作为测试用例(取自挑战)：

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

repr = "1 : 0 : 1 : 0 : 0 : 1 : 1 : 0 : 0";
train = Train.fromRepr(repr);
assertEquals(9, sol.howManyWagons(train), repr);
}

}

所以，当只有一辆马车时，它确实算在内。然而，我们怎么能把它变成将军呢？因为如果我们有5辆货车(第二次测试)，如："1:0:1:0:0"，代码输出：

first: 1
next: 0
prev: 0

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

另外，我读过：

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

我们如何计算双链表(循环列表)中的元素，其中我们不知道初始状态，也不知道头/尾在哪里‽

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

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

Answer 1

记录当前车厢中的灯光状态。然后，在candidateWagonCount从1到无穷大(或到Integer.MAX_VALUE)的循环中，查看列车中是否有candidateWagonCount车厢。此检查按如下方式进行：

1. 关灯
2. 向前移动candidateWagonCount车厢。如果灯亮着，我们就知道火车上不可能有candidateWagonCount车厢。将candidateWagonCount移回原来的位置，然后进行下一次迭代
3. 如果灯熄灭，我们可能已经回到了起点。现在把candidateWagonCount车厢移回我们知道的起点。开灯。再次向前移动candidateWagonCount车厢。如果灯现在亮着，我们就知道我们已经回到了起点。因此，列车上必须有candidateWagonCount车厢。将灯光设置为其原始状态(打开或关闭)并退出。否则，将candidateWagonCount车厢移回起始位置

在我看来，困难在于不知道起点或终点在哪里，因为火车是圆形的，所以没有起点或终点。你不妨考虑一下火车起点的位置。

对我来说，挑战在于我们如何知道何时绕了一整圈。如果我们只是在火车上向一个方向移动，即使我们认出了之前离开的灯的图案，我们也不知道我们是回到了，还是来到了一个恰好具有相同图案的新系列。解决方案是在关闭某个灯和打开某个灯后采取相同的步骤。

Answer 2

Ole V.V.为这个问题提供了一个出色的解决方案，我在Java:中实现了该算法

public int howManyWagons(Train train){
boolean end = false;
int count = 1;

while(!end){ 

//save the state of the first wagon
boolean isFirstWgonLightOn = train.isLightOnInCurrentWagon();

//light off in the first wagon
if(train.isLightOnInCurrentWagon()){
train.switchLight();
}

//go n forward
goFoward(train,count);

if(train.isLightOnInCurrentWagon()){
goBack(train,count);
count++;
}else{

train.switchLight();
goBack(train,count);

if(train.isLightOnInCurrentWagon()){
end=true;
}else{

//we need to reset the ligt state
goFoward(train,count);
train.switchLight();
goBack(train,count);
count++;

}
}

//we need to reset to the initial state
if(isFirstWgonLightOn != train.isLightOnInCurrentWagon()){
train.switchLight();
}

} 
return count;

}

Answer 3

最初在同一辆马车上启动两个指针p1和p2。把p1留在那节车厢里，然后把p2一节一节地运过火车，计算步数。当p2返回到p1仍指向的同一车厢时停止。

当p2移动时，如果马车灯光与p1处的灯光不同，则p2处于不同的马车处。如果灯光相同，则在p2处翻转灯光。如果p1处的光没有改变，那么p2处于不同的马车上。如果在翻转p2时p1处的灯光发生变化，则两个指针都指向同一辆马车。检查p2移动了多远，看看火车有多长。

ETA(感谢疯狂物理学家)：宣布两个马车而不是两个指针。保持w1(=p1)固定，移动w2(=p2)。假设他们在火车上的不同点开始移动w2，直到翻转w2的灯显示它与w1在同一车厢。然后遵循与上面相同的想法。

计算w2移动了多远可以让你开始计算火车的长度——那些车厢不是w1。