单向环形列表的应用场景

约瑟夫问题
数据结构——简单应用单链表

约瑟夫问题

Josephu 问题为: 设编号为1, 2, .. n的n个人围坐一圈，约定编号为k (1<=k<=n)的人从1开始报数，数到m的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。

**提示**: 用一个不带头结点的循环链表来处理Josephu问题: 先构成一个有 n个结点的单循环链表，然后由k结
点起从1开始计数，计到m时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从1开始计数，直
到最后一个结点从链表中删除算法结束。

单向环形链表

约瑟夫问题分析图

代码实现分析：

先创建一个单项环形链表
1. 先创建第一个节点，让first指向该节点，并形成环形
2. 后边当我们每创建一个新的节点，就把该节点，加到已有的环形链表中即可
遍历环形链表
1. 先让一个辅助指针（temp），指向first
2. 然后通过一个while循环遍历该链表即可 ( temp.next=first)遍历结束
  
  这里有张图片：
生成小孩出圈的顺序
1. 先创建一个辅助指针（helper），让它指向环形链表的最后一个
2. 报数前，先让first和helper移动到startNo
3. 当小孩报数时，让first与helper同时移动m-1次
4. 这时first指向的小孩出圈
  first=first.next helper.next=first
5. 此时原来first指向的节点就会被回收
  
  这里有张图片：

创建节点的代码

//先创建一个Child类表示一个节点
class Child {
    private int no;
    private Child next;  //指向下一个节点，默认null

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

    public int getNo ( ) {
        return no;
    }

    public void setNo ( int no ) {
        this.no = no;
    }

    public Child getNext ( ) {
        return next;
    }

    public void setNext ( Child next ) {
        this.next = next;
    }
}

创建环形链表的代码

//创建一个环形的单向链表
class CireSingleLinkedList {
    //创建一个first节点，没有编号
    private Child first = new Child ( -1 );

    //添加小孩节点，构建一个环形链表
    public void CreatChildList ( int nums ) {
        //对nums 进行数据校验
        if ( nums < 1 ) {
            System.out.println ( "nums的值不正确" );
            return;
        }
        //创建环形链表
        Child temp = null;   //辅助指针，帮助构建环形指针
        for ( int i = 1 ; i <= nums ; i++ ) {
            //根据编号创建小孩节点
            Child boy = new Child ( i );
            //如果是第一个小孩
            if ( i == 1 ) {
                first = boy;
                first.setNext ( first );
                temp = first;
            }
            else {
                temp.setNext ( boy );//把之前最的后辅助节点的next指向新加的
                boy.setNext ( first );//此时处在最后的节点的next指向first
                temp = boy;  //辅助节点往后移
            }
        }
    }

    //遍历环形链表
    public void list ( ) {
        //判断链表是否为空
        if ( first == null ) {
            System.out.println ( "链表为空，没有任何小孩\n" );
            return;
        }
        //因为first不能动，所以我们仍然使用一个辅助指针完成遍历
        Child temp = first;
        while (true) {  //满足条件说明已经是最后一个，遍历完毕
            System.out.printf ( "小孩的编号为%d\n", temp.getNo ( ) );
            if ( temp.getNext ( ) == first ) {
                return;
            }
            temp = temp.getNext ( );//后移
        }
    }
}

小孩出圈顺序代码

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

/**
 * @param startNo  开始节点  ，表示从第几个小孩开始
 * @param countNum 每次数几下（m）
 * @param nums     表示最初有几个人
 */
public void countBoy ( int startNo, int countNum, int nums ) {
    //先对数据进行校验
    if ( first == null || startNo < 1 || startNo > nums ) {
        System.out.println ( "参数输入有误，请从新输入" );
        return;
    }
    //先创建一个辅助指针（helper），让它指向环形链表的最后一个
    Child helper = first;
    while (true) {
        if ( helper.getNext ( ) == first ) {  //说明helper指向最后一个节点
            break;
        }
        helper = helper.getNext ( );
    }
    //先将first移动到startNo节点
    for ( int j = 0 ; j < startNo - 1 ; j++ ) {
        first=first.getNext ( );
        helper = helper.getNext ( );
    }
    //当小孩报数时，让first与helper同时移动m-1次,然后出圈
    //这里是一个循环操作，直到圈中只有一个节点
    while (helper!=first) {   //helper==first(helper.getnext()==helper)说明圈中只有一个节点
        //让first与helper同时移动countNum-1次
        for ( int j = 0 ; j < countNum - 1 ; j++ ) {
            first=first.getNext ( );
            helper = helper.getNext ( );
        }
        //此时first指向的节点是要出圈的小孩
        System.out.printf ( "小孩%d出圈\n", first.getNo ( ) );
        //将此时first指向的小孩弄出圈
        first = first.getNext ( );
        helper.setNext ( first );
    }
    System.out.printf ( "最后留在圈中的小孩编号%d\n",first.getNo () );
}