- 一道和循环链表相关的算法题
-
有100人按编号从1到100围成一个圈，从第一个人开始报数，报道数字5的时候把报数字3的人踢出去，然后从报数字5的下一个人继续报数字1，在这个圈子里一直报下去，最后报到剩下一个人结束报数。那么最后剩下的那个人的编号是多少？
-
- Martin-wwh 嗯，谢谢大佬提示
- 大约 2 年之前 回复
用Java实现的代码，仅供参考
LinkedList<Integer> list = new LinkedList<Integer>();
for (int i = 0; i < 100; i++) {//初始化100个人
list.add(i+1);
}
int count = 1;//报数1-5，从1开始报
int curIndex = 0;//当前报数人下标，从第一个人开始报数
int removeIndex = 0;//要移除的报数人下标
while(list.size() > 1){//剩下最后一个人的时候退出
if(count == 3)//报到3时，记录当前报数人下标，用于移除
removeIndex = curIndex;
if(count == 5){//报到5时
count = 0;//重新报数
list.remove(removeIndex);//移除报数3的人
if(removeIndex <= curIndex)//移除的人在报数5的前面时，报数5的下标往前移一位
curIndex--;
}
count++;//下一个要报的数
curIndex++;//下一位报数人下标
if(curIndex >= list.size()){//最后一位报数完，回到第一位继续报数
curIndex = 0;
}
}
System.out.println(list.element());//输出剩下的最后一位的编号
-
- Martin-wwh 谢谢你的代码，我用循环链表也实现出来了
- 大约 2 年之前 回复
