环形链表之约瑟夫问题

约瑟夫问题

约瑟夫.jpg

构建环形单向链表

• 先创建第一个节点,让first指向该节点,并形成环形
• 后面当我们每创建一个新的节点,就把该节点,加入到已有的环形链表即可

遍历环形链表

• 先让一个辅助指针curBoy指向first节点
• 然后通过一个while循环遍历该环形链表即可curBoy.next == first结束

curBoy指针

约瑟夫问题解析

代码

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 CircleSingleLinked {
    //定义first指向第一个
    Boy first = null;

    public void add(int num) {
        if (num < 1) {
            System.out.println("小孩个数不能少于一个");
            return;
        }
        //定义辅助指针
        Boy curBoy = null;
        for (int i = 0; i < num; i++) {
            if (i == 0) {
                first = new Boy(i);
                first.setNext(first); //当只有一个时,指向自己形成环形
                curBoy = first;
            } else {
                Boy boy = new Boy(i);
                curBoy.setNext(boy);
                curBoy = boy;
                curBoy.setNext(first);
            }
        }
    }

    public void list() {
        if (first == null) {
            System.out.println("链表为空");
            return;
        }
        Boy curBoy = first;
        while (true) {
            System.out.println("boy编号为:" + curBoy.getNo());
            if (curBoy.getNext() == first) {
                break;
            }
            curBoy = curBoy.getNext();
        }
    }

    /**
     * 小孩出圈
     * @param startNum 从第几个小孩开始
     * @param countNum 数几下出去
     * @param total    总人数
     */
    public void countBoy(int startNum, int countNum, int total) {
        if (startNum > total || total < 1 || countNum < 1) {
            System.out.println("参数错误!!");
            return;
        }
        Boy helper = first;
        /*把helper指针移到最后一个*/
        while (true) {
            if (helper.getNext() == first) {
                break;
            }
            helper = helper.getNext();
        }
        /*从第几个小孩数*/
        for (int i = 0; i < startNum - 1; i++) {
            first = first.getNext();
            helper = helper.getNext();
        }

        /*开始数数出圈*/
        while (true){
            if(helper == first){ //此时圈中只有一人
                System.out.println("最后出圈的人的序号为:"+ helper.getNo());
                break;
            }
            //开始数数 要数自己就只需要移动countNum - 1
            for (int i = 0; i < countNum - 1; i++) {
                first = first.getNext();
                helper = helper.getNext();
            }
            //开始出圈
            System.out.println("出圈小孩序号为:"+first.getNo());
            first = first.getNext();//使用赋值直接丢弃出圈
            helper.setNext(first);//用setNext进行连接
        }
    }
}

/**
 * 约瑟夫问题 小孩出圈 ---- 环形单向链表
 */
public class CircleSingleLinkedDemo {
    public static void main(String[] args) {
        CircleSingleLinked linked = new CircleSingleLinked();
        linked.add(5);
        linked.countBoy(1,2,5);
    }
}