约瑟夫环问题：循环链表解法

约瑟夫环问题：循环链表解法

问题描述

有n个人编号为1~n，排成一个环，从1号人开始从1到m报数，报到m的人离开该环，从下一个人开始继续从1到m报数，报到m的人离开该环，...，这样一直进行下去，直到最终剩余p个人。从键盘输入n、m、p，要求n>=2、m>=2、p<n，输出最终剩余的p个初始编号。

解决方案说明

1. 逻辑结构: 采用循环链表来表示人员的环，因为循环链表可以很方便地实现环形结构，并且可以很容易地删除指定位置的元素。
2. 物理结构: 采用链表来实现循环链表，因为链表可以动态地添加和删除元素，并且可以通过指针来实现元素之间的连接。
3. 解决问题的思路和方法:
   • 首先，根据输入的n、m、p创建一个循环链表，并初始化编号为1到n的人员。
   • 然后，从编号为1的人开始循环报数，每次报到m的人就从链表中删除。
   • 直到剩下p个人为止，输出它们的初始编号。

具体流程

1. 从键盘输入n、m、p。
2. 创建一个循环链表，并初始化编号为1到n的人员。
3. 设置当前指针指向链表的第一个节点。
4. 从1开始循环报数，直到剩下p个人为止：
   • 报数到m的人，即当前指针指向的节点，从链表中删除。
   • 将当前指针指向下一个节点。
5. 输出剩下p个人的初始编号。

这样可以保证每次报数到m的人都能被正确删除，并且最终剩下的p个人即为最终答案。