简洁明了！Java实现单向环形链表以解决约瑟夫环Josepfu问题

文章目录

• • 简单介绍
  • 代码实现

---

简单介绍

如果把单链表的最后一个节点的指针指向链表头部，而不是指向NULL，那么就构成了一个单向循环链表，通俗讲就是让尾节点指向头结点。

单向环形链表应用场景：Josephu(约瑟夫、约瑟夫环)问题：
设编号为1, 2, … n的n个人围坐一圈，约定编号为k (1<=k<=n)的人从1开始报数，数到m的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。

---

代码实现

节点类

//节点类 class JNode {private int id;private JNode next;public JNode(int id) {this.id = id;}public int getId() {return id;}public JNode getNext() {return next;}public void setNext(JNode next) {this.next = next;}}

链表类（包括节点管理和约瑟夫环问题解决）

//链表类 class CircleSingleLinkedList {private JNode first = null; //定义第一个节点，未创建时为null//添加节点，构建环形链表public void add(int num) {if (num < 1){System.out.println("创建个数不符合规定！");return;}JNode curNode = null; //辅助变量for (int i = 1; i <= num; i++) {JNode newNode = new JNode(i);if (i == 1){ //第一个节点较为特殊first = newNode; //真正创建了第一个节点first.setNext(first); //形成环状curNode = first; //让辅助变量开始作用}else { //第二个及其之后节点curNode.setNext(newNode); //让当前节点指向新建的节点newNode.setNext(first); //让新建的节点指向第一个节点，形成环状curNode = newNode; //更新辅助变量}}}//遍历链表public void list(){if (first == null){System.out.println("链表为空！");return;}JNode temp = first;while (true){System.out.printf("取出节点%d\n",temp.getId());if (temp.getNext() == first){ //说明已经遍历到最后一个了break;}temp = temp.getNext();}}//根据参数让节点出圈（Josepfu）public void josepfu(int startNode,int count,int num){ //startNode为开始的那个节点，count为每次数第几个，num为链表节点个数if (first == null || startNode < 1 || count < 1 || startNode > num){System.out.println("链表为空或者输入的参数不符合标准！");return;}//让first移动到startNode指定的节点，即移动startNode-1次for (int i = 0; i < startNode - 1; i++) {first = first.getNext();}//创建一个辅助变量，让其指向最后一个节点（first前一个）JNode helper = first;while (helper.getNext() != first){helper = helper.getNext();}//开始按照要求出圈，每次都让helper和first移动count-1次while (true){if (helper == first){ //圈中只剩下一个节点break;}for (int i = 0; i < count - 1; i++) {first = first.getNext();helper = helper.getNext();}//此时first指向的即为要出圈的节点System.out.printf("节点%d出圈\n",first.getId());//将出圈的节点从链表中移除first = first.getNext();helper.setNext(first);}System.out.printf("节点%d为最后一个节点",first.getId());} }

测试类

/*** @Author: Yeman* @Date: 2021-10-15-22:33* @Description:*/ public class JosepfuTest {public static void main(String[] args) {CircleSingleLinkedList linkedList = new CircleSingleLinkedList();linkedList.add(5);linkedList.list();System.out.println("===================");linkedList.josepfu(1,2,5);} }

总结

以上是生活随笔为你收集整理的简洁明了！Java实现单向环形链表以解决约瑟夫环Josepfu问题的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。