Java两种方式实现约瑟夫环完整版

package test1;

/**
 * 约瑟夫环(单向链表)
 * 
 * @author Xu Yiqing
 *
 */
public class JosephCircle1 {

    private MyLinkedList linkedlist;
    private Integer size;

    /**
     * 由单向链表生成单向循环链表
     * 
     * @param linkedlist 单项链表
     * @return 生成的约瑟夫环的第一个Node
     */
    public Node<Integer> getJosephCircle(MyLinkedList linkedlist) {
        try {
            this.linkedlist = linkedlist;
            this.size = this.linkedlist.getLinkedListSize();
            
            Node<Integer> head = linkedlist.getHeadNode();
            Node<Integer> tail = linkedlist.getLastNode();
            tail.setNext(head);
            
            this.linkedlist.beginNode = null;
            
            return head;
        } catch (Exception e) {
            e.printStackTrace();
            return null;
        }
    }

    /**
     * 删除约瑟夫环的一个Node
     * 
     * @param node 想要删除的Node
     * @return 返回删除Node的前一个Node
     */
    @SuppressWarnings({ "rawtypes", "unchecked" })
    public Node deleteFromCircle(Node node) {
        
        Node flag = node.next;
        
        for (int i = 0; i < this.size - 2; i++) {
            flag = flag.next;
        }
        flag.next = flag.next.next;
        
        node = flag;
        
        this.size--;
        return node;
    }

    /**
     * 自定义链表类
     * 
     * @author Xu Yiqing
     *
     */
    static class MyLinkedList {
        private Integer size;
        @SuppressWarnings("rawtypes")
        private Node beginNode;

        /**
         * 构造方法
         */
        public MyLinkedList() {
            doClear();
            
            this.beginNode = new JosephCircle1().new Node<Integer>(null, null);
        }

        /**
         * 获取第一个Node
         * 
         * @return 第一个Node
         */
        @SuppressWarnings("unchecked")
        public Node<Integer> getHeadNode() {
            return beginNode.next;
        }

        /**
         * 在尾部添加一个新Node
         * 
         * @param value Node的值
         */
        @SuppressWarnings({ "rawtypes", "unchecked" })
        public void addAtTail(Integer value) {
            Node newNode = new JosephCircle1().new Node<Integer>(value, null);
            if (this.size == 0) {
                beginNode.next = newNode;
            } else {
                getNode(this.size - 1).next = newNode;
            }
            this.size++;
        }

        /**
         * 获取指定的Node
         * 
         * @param index Node索引
         * @return 获取到的Node
         */
        @SuppressWarnings({ "finally", "unchecked" })
        public Node<Integer> getNode(Integer index) {
            if (index < 0 || index >= size) {
                try {
                    throw new Exception("越界");
                } catch (Exception e) {
                    e.printStackTrace();
                } finally {
                    return null;
                }
            } else {
                @SuppressWarnings("rawtypes")
                Node flag = beginNode;
                for (int i = 0; i <= index; i++) {
                    flag = flag.getNext();
                }
                return flag;
            }

        }

        /**
         * 删除指定的Node
         * 
         * @param index 删除的Node的索引
         */
        @SuppressWarnings({ "rawtypes", "finally", "unchecked" })
        public void deleteNode(Integer index) {
            if (index < 0 || index >= size) {
                try {
                    throw new Exception("越界");
                } catch (Exception e) {
                    e.printStackTrace();
                } finally {
                    return;
                }
            } else {
                if (this.beginNode != null) {
                    Node flag = beginNode;
                    for (int i = 0; i <= index; i++) {
                        flag = flag.getNext();
                    }
                    flag.next = flag.getNext().getNext();
                }
            }
            this.size--;
        }

        /**
         * 清空链表
         */
        private void doClear() {
            this.size = 0;
            this.beginNode = null;
        }

        /**
         * 获取最后一个Node
         * 
         * @return 最后一个Node
         */
        public Node<Integer> getLastNode() {
            return getNode(this.size - 1);

        }

        /**
         * 获取链表的大小
         * 
         * @return 大小
         */
        @SuppressWarnings("unchecked")
        public Integer getLinkedListSize() {
            Integer size = 0;
            Node<Integer> flag = beginNode;
            while ((flag = flag.getNext()) != null) {
                size++;
            }
            return size;
        }
    }

    /**
     * 自定义链表节点
     * 
     * @author Xu Yiqing
     *
     * @param <Type> 泛型
     */
    class Node<Type> {

        private Type value;
        private Node<Type> next;

        public Node(Type value, Node<Type> next) {
            super();
            this.value = value;
            this.next = next;
        }

        public Type getValue() {
            return value;
        }

        public void setValue(Type value) {
            this.value = value;
        }

        public Node<Type> getNext() {
            return next;
        }

        public void setNext(Node<Type> next) {
            this.next = next;
        }

    }

}

package test1;

import java.util.Scanner;

import test1.JosephCircle1.MyLinkedList;
import test1.JosephCircle1.Node;
/**
 * 测试类
 * @author Xu Yiqing
 *
 */
public class Test1 {
    @SuppressWarnings("rawtypes")
    public static void main(String[] args) {
        JosephCircle1 circle = new JosephCircle1();
        MyLinkedList linkedlist = new MyLinkedList();
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int num = sc.nextInt();
        for (int i = 0; i < num; i++) {
            linkedlist.addAtTail(i + 1);
        }
        Node node = circle.getJosephCircle(linkedlist);

        for(int i=0;i<num;i++) {
            for (int j = 0; j < (m-1); j++) {
                node = node.getNext();
            }
            //由于要删除，需要先显示出来
            System.out.print(node.getValue());
            
            node=circle.deleteFromCircle(node);
            node=node.getNext();

        }
        sc.close();
    }
    
}

package test1;

/**
 * 顺序表实现约瑟夫环
 * 
 * @author Xu Yiqing
 *
 */
public class JosephCircle2 {

    /**
     * 约瑟夫环构造方法
     * 
     * @param number   将数据添加到顺序表
     * @param start    约瑟夫环开始索引
     * @param distance 删除元素间隔
     */
    public JosephCircle2(int number[], int start, int distance) {
        MyLinearList list = new MyLinearList(number.length);
        for (int i = 0; i < number.length; i++) {
            list.append(number[i]);
        }
        int i = start;
        while (list.length() > 1) {
            i = (i + distance - 1) % list.length();
            System.out.print(list.get(i));
            list.remove(i);
        }
        System.out.print(list.get(0));
    }

    /**
     * 自定义顺序表
     * 
     * @author Xu Yiqing
     *
     */
    class MyLinearList {
        private Integer[] elements;
        private Integer len;

        /**
         * 构造方法
         * 
         * @param 拷贝顺序表
         */
        public MyLinearList(MyLinearList list) {
            this.len = list.len;
            this.elements = new Integer[list.elements.length];
            for (int i = 0; i < list.elements.length; i++) {
                this.elements[i] = list.elements[i];
            }

        }

        /**
         * 构造方法
         * 
         * @param size 大小
         */
        public MyLinearList(int size) {
            this.elements = new Integer[size];
            this.len = 0;
        }

        /**
         * 判空
         * 
         * @return
         */
        public boolean isEmpty() {
            return this.len == 0;
        }

        /**
         * 大小
         * 
         * @return 大小
         */
        public int length() {
            return this.len;
        }

        /**
         * 获取某个元素
         * 
         * @param index 所有
         * @return 元素
         */
        public Integer get(int index) {
            if (index >= 0 && index < this.len) {
                return this.elements[index];
            } else {
                return null;
            }
        }

        /**
         * 设置某个元素
         * 
         * @param i     索引
         * @param value 值
         */
        public void set(int i, Integer value) {
            if (i >= 0 && i < this.len)
                this.elements[i] = value;
            else
                try {
                    throw new Exception("无法设置");
                } catch (Exception e) {
                    e.printStackTrace();
                }

        }

        /**
         * 插入某个元素
         * 
         * @param i     索引
         * @param value 值
         */
        public void insert(int i, Integer value) {
            if (i < 0) {
                i = 0;
            }
            if (i > this.len) {
                i = this.len;
            }
            if (this.len == this.elements.length) {
                Integer[] temp = this.elements;
                this.elements = new Integer[this.elements.length + 1];
                for (int j = 0; j < temp.length; j++) {
                    this.elements[j] = temp[j];
                }
            }

            for (int j = this.len - 1; j >= i; j--) {
                this.elements[j + 1] = this.elements[j];
            }
            this.elements[i] = value;
            this.len++;
        }

        /**
         * 在尾部添加
         * 
         * @param value 值
         */
        public void append(Integer value) {
            this.insert(this.len, value);
        }

        /**
         * 删除某个元素
         * 
         * @param i 索引
         * @return 删除是否成功
         */
        public boolean remove(int i) {
            if (this.len == 0 || i < 0 || i >= this.len) {
                return false;
            }
            for (int j = i; j < this.len - 1; j++) {
                this.elements[j] = this.elements[j + 1];
            }
            this.elements[this.len - 1] = null;
            this.len--;
            return true;
        }

        /**
         * 清除
         * 
         * @return
         */
        public boolean removeAll() {
            this.len = 0;
            return true;
        }

        /**
         * 销毁
         * 
         * @return
         */
        public boolean destroy() {
            this.removeAll();
            this.elements = null;
            return true;
        }

        /**
         * 搜寻某个元素是否存在
         * 
         * @param value 值
         * @return 找不到返回-1
         */
        public Integer search(Integer value) {
            int index = this.indexOf(value);
            return index == -1 ? null : this.elements[index];
        }

        /**
         * 根据值定位第一个索引
         * 
         * @param value 值
         * @return 第一个索引
         */
        private int indexOf(Integer value) {

            for (int i = 0; i < this.len; i++) {
                if (this.elements[i].equals(value)) {
                    return i;
                }
            }
            return -1;

        }

        /**
         * 是否包含
         * 
         * @param value 值
         * @return 第一个值的索引
         */
        public boolean contain(Integer value) {
            return this.indexOf(value) >= 0;
        }

        /**
         * 判断某个对象是否和该顺序表一致
         */
        public boolean equals(Object object) {
            if (this == object)
                return true;
            if (object instanceof MyLinearList) {
                MyLinearList list = (MyLinearList) object;
                if (list.length() == this.length()) {
                    for (int i = 0; i < list.length(); i++) {
                        if (!this.get(i).equals(list.get(i)))
                            return false;
                    }
                    return true;
                }
            }
            return false;
        }
    }

}

package test1;

import java.util.Scanner;
/**
 * 测试类
 * @author Xu Yiqing
 *
 */
public class Test2 {
    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int n=sc.nextInt();
        
        int[] arr=new int[n];
        for(int i=0;i<arr.length;i++) {
            arr[i]=i+1;
        }
        new JosephCircle2(arr, 0, m);
        sc.close();

    }
}