约瑟夫问题

设编号1，2........n的那个人围坐一圈，约定编号k(1<=k<=n)的人从开始报数，数到m的那个出列，从它的下一位又开始从1开始报数，数到m的那个人又出列，以此类推，直到剩下一个人；

解决方法：使用一个不带头节点的循环链表来处理，先构成一个有n个结点的循环链表，然后从k结点起1开始计数，记到m时，对应结点从链表中删除，然后再从被删除的结点的下一个结点又开始从1计数，直到剩下一个结点为止；

代码实现

1）创建单链表

先创建第一个结点，让first指向第一个结点，并形成环：first.next = first

后面每创建一个结点，就加入到已有的环中；

2）出圈的方法解析：

① 需要创建一个辅助指针helper,让它总是指向最后一个结点的位置；

② 假设起始位置为startNum, 那么helper指针和first都要移动startNum-1次；

③ 然后小孩开始报数，假如报数m下，那么helper和first都要移动m-1次，移动后first位置的孩子为要出圈的孩子，则：first = first.next (first后移); helper.next = first;

④ 直到first == helper的时候剩下一个结点；

public class JosepfuList {
    public static void main(String[] args) {
        forList forList = new forList();
        forList.setFroArr(5);
     //   forList.getList();
       forList.countBoy(1,2,5);
    }
}
class forList {
    private Node first = null;

    //创建环形链表
    public void setFroArr(int nums) {
        if (nums<1) {
            System.out.println("输入正确的数量");
            return;
        }
        Node curr = null;  //辅助结点
        for (int i =1; i<=nums; i++) {
            // 创建结点
            Node body = new Node(i);
            if (i==1) {
               first = body; //将该节点设置为first结点
               curr = first;
              curr.next = first;
            } else {
                curr.next = body;
                body.next = first;
                curr = body;
            }
        }
    }

    // 根据用户输入，计算出小孩出小孩顺序

    /**
     *
     * @param startNo 从第几个开始
     * @param countNum 数几个数
     * @param nums 孩子总数
     */
    public void countBoy(int startNo, int countNum, int nums){
         if (startNo < 1 || countNum > nums || first==null) {
             System.out.println("请输入正确数据");
             return;
         }
         Node helper = first; // 辅助指针，让其指向最后一个结点
        while (true) {
            if (helper.next == first) {
                break;
            }
            helper =helper.next;
        }
        /**
         * 在报数前让first和helper移动到startNo-1次
         */
       for (int i=0;i<startNo-1;i++) {
           helper = helper.next;
           first = first.next;
       }
       // 小孩开始报数，让first和helper指针同时移动countNum-1次，然后出圈，直到圈中只有一个结点

        while (true) {
            if (first == helper) {
               break;
            }
           //让first和helper指针同时移动countNum-1次,first指向要出圈的结点
           for (int j=0; j<countNum-1; j++) {
               first = first.next;
               helper = helper.next;
           }
            System.out.println(first.no);
           first = first.next;
           helper.next = first;
        }
        System.out.println(first.no);
    }

    // 遍历环形链表
    public void getList() {
        if (first == null) {
            System.out.println("链表为null");
            return;
        }
        Node curr = first;
        while (true) {
            if (curr.next == first) {
                System.out.println(curr.no);
               return;
            }
            System.out.println(curr.no);
            curr = curr.next;
        }
    }
}
// 创建一个结点
class Node {
    public int no;
    public Node next;

    public Node(int no) {
        this.no = no;
    }

    @Override
    public String toString() {
        return "Node{" +
                "no=" + no +
                '}';
    }
}