环形链表方法解决约瑟夫环问题（JAVA）

    编号是1，2...n的n个人围坐一圈，编号为k（1<=k<=n）的人从1开始报数，每数到第m个，该人就要离开此圈，它的下一位从1开始报数，数到m出列，这样依次下来，直到圈中所有人出列，最后产生一个出队编号。

目录

一、首先编写一个节点类

二、问题解决思路

三、省略部分对应代码

四、测试代码

一、首先编写一个节点类

public class Node {      //节点编号(题中人的编号)     private int id;     //下一个节点     private Node next;      public Node(int id) {         this.id = id;     }      public int getId() {         return id;     }      public void setId(int id) {         this.id = id;     }      public Node getNext() {         return next;     }      public void setNext(Node next) {         this.next = next;     }      @Override     public String toString() {         return "Node{" +                 "id=" + id +                 '}';     } }

二、问题解决思路

定义一个头节点，不代表题中任何人的编号；

1. 添加节点；
2. 查看环形链表中的所有节点；
3. 根据题意，编写对应代码。

省略代码在第三部分

public class CSLinkedList {      //头节点，编号不计算     public Node first = new Node(-1);       /**      * 为环形链表添加节点      * @param num 环形链表的节点个数      */     public void addNode(int num){         //代码     }       /**      * 查看环形链表中所有的节点      */     public void showNode(){           //代码     }           /**      * 约瑟夫环问题      * @param start 开始报数人的编号：编号为k（1<=k<=n）的人从1开始报数      * @param count 离开时报的数：每数到第m个，该人就要离开此圈，它的下一位又从1开始报数      * @param num 圈内人数：编号是1，2...n的n个人围坐一圈      */     public void josephCircle(int start, int count, int num){         //代码     }  } 

三、省略部分对应代码

1、添加节点

    /**      * 为环形链表添加节点      * @param num 环形链表的节点个数      */     public void addNode(int num){          //判断num         if (num < 1){             System.out.println("不符合要求！");             return;         }          //临时节点         //添加临时节点，只用更改临时节点指向的节点即可，不需要对环形链表中的节点进行复杂操作         Node temp = null;          for (int i = 1; i <= num; i++) {              //新节点             //从编号1开始，每循环一次，添加一个新节点             Node node = new Node(i);              //判断添加方式             if (i == 1){                 //第一个节点的添加                 //使编号为1的节点为第一个节点，第一个节点的下一个节点指向自身。                 first = node;                 first.setNext(first);                 //使编号为1的节点指向临时节点，方便以后的添加操作                 temp = first;             }else {                 //其它节点的添加                 //使临时节点指向新添加的节点                 temp.setNext(node);                 //新添加的节点指向编号为1的节点                 node.setNext(first);                 //使新添加的节点指向临时节点，方便以后操作                 temp = node;              }           }       }

2、查看环形链表中的所有节点

public void showNode(){                  if (first.getNext() == null){             System.out.println("该环形链表为空！");             return;         }          Node node = first;          while (true){             //输出每一个节点的编号             System.out.printf("编号为%d\n",node.getId());              //节点的下一个节点指向第一个节点时，循环结束             if(node.getNext() == first){                 break;             }             //使节点向后移动             node = node.getNext();         }     }

3、约瑟夫环问题相关代码

public void josephCircle(int start, int count, int num){           //判断输入是否正确         if (first == null || start < 1 || count > num){             System.out.println("输入有错误！");             return;         }          //定义一个结束节点，指向环形链表的最后一个元素         Node end = first;         while (end.getNext() != first){             end = end.getNext();         }          //定义一个开始节点         //开始报数人的编号为2,则first节点移动2-1次         //first节点移动，结束节点（end）也会移动，移动次数和first节点相同         for (int i = 0; i < start - 1; i++) {             first = first.getNext();             end = end.getNext();         }          //出列节点         //判断节点个数，只有一个节点         while (end != first){              //判断出列节点             //报3的人出列，first是编号为2的人，则移动3-1次，编号为4的人出列，             for (int i = 0; i < count - 1; i++) {                 first = first.getNext();                 end = end.getNext();             }              System.out.printf("编号-%d-节点出环形链表！\n",first.getId());              first = first.getNext();             end.setNext(first);         }         System.out.printf("编号-%d-节点出环形链表！\n",first.getId());     }

四、测试代码

public class Test01 {     public static void main(String[] args) {         Node node1 = new Node(1);          CSLinkedList list = new CSLinkedList();          list.addNode(15);         list.showNode();         System.out.println("-------------------");         list.josephCircle(1,2,15);     } }

测试结果如下：

  这是我在书里面看的，书名记不太清，看到就是缘分！

互联网时代，我们即将看到，无创造则无毁灭。

        以上仅供学习参考，可能会有不正确的地方，不过问题应该不大吧，注释是我的想法，表述可能有一点点粗糙，希望可以帮助大家！