[数据结构与算法]数据结构与算法——单向环形链表（约瑟夫问题）

约瑟夫环：假如环中有n个元素，从编号为k（1<=k<=n）的元素开始从1编号，数到m（此图m=3）的元素拿出，它的下一个元素又从1开始编号，数到m的元素再次拿出，以此类推，直至所有的元素被拿出，由此产生一个出队编号。(则下图所示出队列序号为:3?6?1?5?2?8?4?7）

思路：

1.构建一个单向环形列表

1）先创建第一个节点，让 first 指向该节点，并形成环形

2）后面创建每一个节点时，就把新节点加入到已有的环形链表中即可

//创建节点类
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{
    //创建一个first节点
    private Boy first = new Boy(-1);

    //添加节点，构建为环形链表
    public void add(int nums){  //num:整个链表中共有几个节点
        //对num做数据校验
        if(nums<1){
            System.out.println("nums的值不正确！");
            return;
        }
        Boy curBoy = null;  //辅助指针，帮助构建环形链表
        for (int i = 1; i <= nums; i++) {
            //根据编号创建节点
            Boy boy = new Boy(i);
            if (i == 1) {  //第一个节点
                first = boy;
                first.setNext(first);  //第一个节点自身成环
                curBoy = first;
            } else {   //添加数据时，先将节点插入，后将指针后移
                curBoy.setNext(boy);
                boy.setNext(first);
                curBoy = boy;
            }
        }
    }
}

2.遍历环形链表

1）先使用辅助指针curBoy指向 first 节点

2）通过while循环遍历该环形链表（curBoy.next == first）

 //遍历当前环形链表
 public void showBoy(){
     //先判断链表是否为空
     if(first == null){
         System.out.println("链表为空！");
         return;
     }
     //使用辅助指针进行遍历
     Boy curBoy = first;
     System.out.println("遍历后结果为（编号）：" );
     while(true){
         System.out.println(curBoy.getNo());
         if(curBoy.getNext() == first){  //说明遍历回第一个节点，既遍历结束
             break;
         }
         curBoy = curBoy.getNext();   //辅助指针后移
     }

3.”出圈“处理

思路：

根据用户的输入，生成一个节点拿出的顺序

1）使用辅助指针?“helper”，事先应该指向环形链表中编号为k节点的前一个节点处

补：开始编号前， first 和 helper 指针先移动 k - 1 次至 k 节点之前

2） 从k节点编号时，让 first 和 helper 指针同时移动 m -1 次

3）将 first 指向的节点“出圈”?，其中 first 原来指向的节点没有被引用，就会被回收

first = first.next；

helper.next = first；

?“出圈”图示：

?

//根据用户的输入形成出圈顺序
/**
 * @param startNo:开始数的节点
 * @param countNo：每数几下出圈
 * @param nums：一共几个节点
 */
public void countBoy(int startNo, int countNo, int nums) {
    //先对数据进行校验
    if (first == null || startNo < 1 || startNo > nums) {
        System.out.println("参数输入有误！请重新输入！");
        return;
    }
    Boy helper = first;
    //1.首先helper指针应该指向环形链表的最后一个节点
    while (true) {
        if (helper.getNext() == first) {  //说明helper指向了最后一个节点
            break;
        }
        helper = helper.getNext();
    }
    //补：编号前，保证first和helper指针移动 startNo-1 次至编号节点前
    for (int j = 0; j < startNo-1; j++) {
        first = first.getNext();
        helper = helper.getNext();
    }
    //2.开始编号，让 first 和 helper 指针同时移动 countNo-1 次至删除节点出
    //此处是一个循环操作，直到圈中没有节点为止
    boolean flag = true;
    while (true){
        if(helper == first){  //圈中只有一个节点
            break;
        }
        //让 first 和 helper 同时移动 countNo - 1 次
        for (int j = 0; j < countNo - 1; j++) {
            first = first.getNext();
            helper = helper.getNext();
        }
        //这时first指向的节点既为要出圈的节点
        System.out.println(first.getNo());
        //将first此时指向的节点出圈
        first = first.getNext();
        helper.setNext(first);
    }
    System.out.println("最后留在圈中的节点为：" + first.getNo());  //此时最后留在圈中的节点同时被helper和first指向
}

?