约瑟夫杀人法

约瑟夫问题：N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。

利用单项循环链表解决

public class Josephus {
    // 游戏人数
    private static int Numbers = 10;
    // 间隔
    private static int Gap = 3;
    
    // 节点类
    class Node<T>{
        T value;
        Node<T> next;
        
        public T getValue() {
            return value;
        }
        
        public void setValue(T value) {
            this.value = value;
        }
    }
    
    public void killPerson(){
        // 创建头节点
        Node<Integer> head = new Node<Integer>();
        head.setValue(1);
        // 让指针指向head
        Node<Integer> pointer = head;
        // 构造循环链表
        for(int i = 2; i <= Numbers; i++){
            Node<Integer> node = new Node<Integer>();
            node.setValue(i);
            pointer.next = node;
            pointer = pointer.next;
        }
        // 最后一个节点指向头节点，这样就构造出了一个单向循环链表
        pointer.next = head;
        
        // 开始杀人
        // 当只剩一个节点时，pointer和pointer指向的节点的next就都指向这最后一个节点了，
        // 所以循环结束条件即为pointer != poiinter.next 
        while(pointer != pointer.next){
            // 从1数到Gap, 此时指针只移动Gap-1次，下一个就是要干掉的节点
            for(int i = 1; i < Gap; i++){
                pointer = pointer.next;
            }
            // 打印下一个节点的值
            System.out.println(pointer.next.getValue() + "被干掉了");
            // 让当前pointer指针指向的节点的next指针指向下一个节点（就是要被干掉的节点）的下一个节点
            // 这样就把节点干掉了
            pointer.next = pointer.next.next;
        }
        System.out.println("只剩" + pointer.getValue() + "活着了");
    }
    
    public static void main(String[] args){
        Josephus josephus = new Josephus();
        josephus.killPerson();
    }
}