1、问题描述

n个人围成一圈，从第k个人开始报数，报到m的人出圈，剩下的人继续从出圈的下一个人开始报数，报到m的人出圈；如此往复，直到所有人出圈。（模拟此过程，输出出圈的人的序号）。

 

2、采用单向循环链表实现

节点

public class HeroNode {    protected Integer no;    protected String name;    protected HeroNode next;    public HeroNode(Integer no, String name) {        this.no = no;        this.name = name;    }    @Override    public String toString() {        return "HeroNode[" +                "no=" + no +                ", name='" + name + '\'' +                ']';    }}

 

单向循环链表：主要通过两个指针实现，first指针指向头节点，tail指向尾节点，再将tail的next指针指向first形成循环单向链表。

public class SingleCiruLinkedList {    protected HeroNode first;    protected HeroNode tail;    /**     * 添加元素，构成单向循环链表     * @param hero     */    public void add(HeroNode hero) {        if (first == null) {            first = hero;            tail = hero;            first.next = first;        } else {            tail.next = hero;            tail = hero;            tail.next = first;        }    }    /**     * 打印     */    public void display() {        if (first == null) {            System.out.println("This SingleCiruLinkedList is null.");            return;        }        HeroNode temp = first;        while(temp != null) {            System.out.println(temp.toString());            temp = temp.next;            if (temp == tail) {                System.out.println(temp.toString());                System.out.println(temp.next.toString());                break;            }        }    }}

 

通过循环单向链表解决约瑟夫问题

public class Joseph {        /**     * @param linkedList 单向循环链表     * @param begin      起始位置     * @param interval   间隔     */    public static void joseph(SingleCiruLinkedList linkedList, int begin, int interval) {        // 根据begin找到开始位置        int i = 0;        while (i < begin - 1) {            linkedList.first = linkedList.first.next;            linkedList.tail = linkedList.tail.next;            i++;        }        while (true) {            // 如果只有一个或者循环到最后一个，打印跳出循环            if (linkedList.first == linkedList.tail) {                System.out.println(linkedList.first.toString());                break;            }            // 每次需要数的次数            int j = 0;            while (j < interval - 1) {                linkedList.first = linkedList.first.next;                linkedList.tail = linkedList.tail.next;                j++;            }            // 最后first指向的就是目标元素，打印            System.out.println(linkedList.first.toString());            // 将目标元素出圈，first指针指向下一个元素，tail的next指针指向first            linkedList.first = linkedList.first.next;            linkedList.tail.next = linkedList.first;        }    }}