❤️一名热爱Java的大一学生,希望与各位大佬共同学习进步❤️
🧑个人主页:@周小末天天开心
各位大佬的点赞👍 收藏⭐ 关注✅,是本人学习的最大动力
感谢!
📕该篇文章收录专栏—数据结构
目录
从判断一个单链表是否存在循环而扩展衍生的问题,有则称之为有环链表问题,也就是经典的约瑟夫问题,也称为约瑟夫环。
如下图所示:
约瑟夫(约瑟夫环,Joseph)问题为:
设编号为1,2,3,……,n 的n个人围坐在一圈,约定编号为k(1 <= k <= n)的人从1开始报数,数到m的那个人出列,他的下一位又从1开始报数,数到m的那个人又出列,以此类推,直到所有人出列为止,由此产生一个出队编号的序列。
例如;
n = 5,即有5个人
k = 1,从第一个人开始报数
m = 2,一次数2下
提示:
用一个不带头节点的循环链表来处理Joseph问题:首先构成一个有 n 个节点的单向环形链表,然后由 k 节点起从 1 开始计数,计数到 m 时,将对应的节点从链表中删除,然后再从被删除的节点的下一个节点又从 1 开始计数,直到最后一个节点从链表中删除,算法结束。
- class Boy {
- private int no;//编号
- private Boy next;//指向下一个节点
- public Boy(int no) {
- this.no = no;
- }
-
- public int getNo() {
- return no;
- }
-
- public void setNo(int no) {
- this.no = no;
- }
-
- public Boy getNext() {
- return next;
- }
-
- public void setNext(Boy next) {
- this.next = next;
- }
- }
- class CircleSingleLinkedList {
-
- }
(1)先创建第一个节点,让 first指向该节点,并形成环形
(2)后面每创建一个新的节点,就把该节点加入到已有的环形列表中即可
- //创建一个 first 节点,当前没有编号
- private Boy first = null;
-
- //添加节点,构成一个环形的链表
- public void addBoy(int nums) {
- //nums 表示节点的总个数
- //对 nums 做数据校验
- if(nums < 1) {
- System.out.println("nums的值不符合条件");
- return;
- }
- Boy curBoy = null;//辅助变量,帮助构造环形节点,因为first不能动
- //使用for循环来创建环形链表
- for (int i = 1; i <= nums; i++) {
- //根据编号,创建节点
- Boy boy = new Boy(i);
- //如果是第一个节点
- if(i == 1) {
- first = boy;//让 first 节点指向自己
- first.setNext(first);//构成环
- curBoy = first;//让 curBoy 指向第一个节点
- } else {
- curBoy.setNext(boy);
- boy.setNext(first);
- curBoy = boy;
- }
- }
- }
(1)先让一个辅助指针(变量)curBoy,指向 first 节点
(2)然后通过一个 while 循环遍历该环形链表即可,curBoy.next == first 时结束
curBoy = first 时开始
curBoy.next == first 时结束
- //遍历该链表
- public void showBoy() {
- //判断该链表是否为空
- if(first == null) {
- //说明该链表为空
- System.out.println("该链表为空");
- return;
- }
- //因为first指向第一个节点不能动,所以需要辅助指针完成遍历
- Boy curBoy = first;
- while(true) {
- System.out.println("节点的编号为" + curBoy.getNo());
- if(curBoy.getNext() == first) {
- //说明链表已经遍历完毕,
- //因为是环形链表,所以curBoy的下一个节点要与first作比较
- break;
- }
- curBoy = curBoy.getNext();//让curBoy后移一位
- }
- }
(1)需要创建一个辅助指针(变量)helper,事先指向环形链表最后的节点
(2)当节点技术前,先让first 和 helper 移动k - 1次
(3)当节点移动时,让 first 和 helper 指针同时移动m - 1次
(4)这时就可以将 first 指向的节点出圈
1)first = first.next;
2)helper.next = first;
(5)原来 first 指向的节点就没有任何引用,就会被回收
- /**
- *
- * @param startNo 表示从第几个节点开始计数
- * @param countNum 表示一次数几下
- * @param nums 表示最初有多少个节点在链表中
- */
- public void countBoy(int startNo , int countNum , int nums){
- //对数据进行校验,保证合理性
- if(first == null || startNo < 1 || startNo > nums) {
- System.out.println("参数输入有误,请从新输入");
- return;
- }
- //创建一个辅助指针,帮助节点出圈
- Boy helper = first;
- //辅助指针 helper 应该事先指向环形链表最后的节点
- while(true){
- if(helper.getNext() == first) {
- //说明helper已经指向了最后的一个节点
- break;
- }
- helper = helper.getNext();
- }
- //节点计数之前,先让 first 和 helper 移动 startNo - 1 次
- for (int i = 0; i < startNo - 1; i++) {
- first = first.getNext();
- helper = helper.getNext();
- }
- //当节点计数时,先让 first 和 helper 指针同时移动 countNum - 1 次,然后出圈
- //这是一个循环操作,知道圈中只有一个节点
- while(true) {
- if(helper == first) {//说明圈中只有一个节点
- break;
- }
- //让 first 和 helper 指针同时移动 countNum - 1 次
- for (int i = 0; i < countNum - 1; i++) {
- first = first.getNext();
- helper = helper.getNext();
- }
- //这时 first 指向的节点就是要出圈的节点
- System.out.printf("节点%d出圈\n",first.getNo());
- //这时可以将 first 指向的小孩节点出圈
- first = first.getNext();
- helper.setNext(first);
- }
- System.out.println("最后留在圈中的节点编号为:" + first.getNo());
- }
- public class Joseph {
- public static void main(String[] args) {
- //构建环形链表
- CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
- circleSingleLinkedList.addBoy(5);
- circleSingleLinkedList.showBoy();
-
- //测试节点出圈
- System.out.println("==============");
- circleSingleLinkedList.countBoy(1,2,5);
- }
- }
当节点为 5 个时的输出结果:
当节点为 10 个时的输出结果: