public static void main(String[] args) {
        //方法1:使用标记+报数器
//        int num = GetLastIndex(5,2);
        //方法2:使用循环链表  正确的返回结果是2
        int num = GetLastIndex2(5, 2);
        System.out.println(num);
    }

    //标记+报数器
    //初始化数组 每个元素都是1

    /**
     * @Description:
     * @Date: 2021/8/9 18:54
     * @Author: fuguowen
     * @Return k个人的索引的下标  比如2代表第三个人
     * @Throws
     */
    public static int GetLastIndex(int k, int p) {
        //k个人
        //p报2
        int[] arr = new int[k];
        //初始化数组都为1
        for (int i = 0; i < arr.length; i++) {
            arr[i] = 1;
        }
        int num = arr.length;
        //报数器
        int flag = 0;
        while (num > 1) {
            for (int i = 0; i < arr.length; i++) {
                if (arr[i] == 1) {
                    flag++;
                    if (flag == p) {
                        //数组清空
                        arr[i] = 0;
                        //报数器清空
                        flag = 0;
                        //数量减一
                        num--;
                    }
                }
            }
        }
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == 1) {
                return i;
            }
        }
        return 0;
    }

    //使用循环链表模拟，报数的人删除对应的节点
    public static int GetLastIndex2(int k, int reportNum) {
        //k个人
        //构建循环链表
        Node head = CreatCycLinkedList(k);

        Node p = head.next;
        //队列中元素只有一个的情况是p.next=p  ☆☆☆☆☆
        while (p.next != p) {
            //p.next指向当前要删除的元素
            for (int i = 0; i < reportNum; i++) {
                p = p.next;
            }
            //删除元素
            p.next = p.next.next;
            //指针下移
            p.next = p;
        }
        return p.next.index;
    }

    public static Node CreatCycLinkedList(int k) {
        //构建循环链表
        Node head = new Node(-1);
        Node cur = head;
        for (int i = 0; i < k; i++) {
            cur.next = new Node(i);
            cur = cur.next;
        }
        cur.next = head.next;
        return head;
    }

//    参考:
//    1.https://www.cxyxiaowu.com/1159.html

public class Node {
    int index;
    Node next;

    public Node( int index) {
        this.index = index;
    }
}