题目

牛客网 - [编程题]环形链表的约瑟夫问题

据说著名犹太历史学家 Josephus 有过以下故事：在罗马人占领乔塔帕特后，39 个犹太人与 Josephus 及他的朋友躲到一个洞中，39 个犹太人决定宁愿死也不要被敌人抓到，于是决定了一种自杀方式，41 个人排成一个圆圈，由第 1 个人开始报数，报数到 3 的人就自杀，然后再由下一个人重新报 1，报数到 3 的人再自杀，这样依次下去，直到剩下最后一个人时，那个人可以自由选择自己的命运。这就是著名的约瑟夫问题。现在请用单向环形链表得出最终存活的人的编号。

一行两个整数 n 和 m， n 表示环形链表的长度， m 表示每次报数到 m 就自杀。

输出最后存活下来的人编号(编号从1开始到n)

输入

5 2

输出

3

注：1 ≤ n , m ≤ 10000

思路

初始化序列成一条链表，并保证每次删除的位置是下一个位置，如果简单的想，6 个人，每 3 个就淘汰，则：

• 1，2，3 ... ，3 被淘汰
• 1，2， x，4，5，6 ... 6 被淘汰

此刻，链表为：1，2，x，4，5，x

如果初始化 6 个人，3 人淘汰一次，则

• position = 0
• 链表 size = 6

那么：

• 第一次是删除 pos = 2（因为 Java 链表从 0 开始），也就是 m - 1，也就是 2
• 第二次是删除 post = m - 1 + m，也就是 2m - 1，也就是 5 ，但并非如此，因为现在链表容量是 5 了，所以应该是 4 ，其实也就是 m - 1 + m - 1 ，也就是 2m - 2 ，也就是 4

如此，每次要取到相对的位置，其实就是类加 m - 1 的过程，但可能会越界，所以要对链表的 size 取模，才不会越界，取模就是相当于环装运算了

初始化 pos = 0（Java 链表从 0 开始），删除间隔为 n，当前链表大小为 list.size()，则有如下运算公式：
$$
下一个淘汰的 pos =(pos + n - 1)%list.size()
$$

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // n 为总人数
        int n = sc.nextInt();
        // m 为淘汰间隔
        int m = sc.nextInt();
        System.out.println(compute(n, m));
    }
    
    private static int compute(int n, int m) {
        List<Integer> list = new LinkedList<>();
        for (int i = 1; i <= n; i++) {
            list.add(i);
        } 
        int pos = 0;
        while (list.size() != 1) {
            pos = (pos + m - 1) % list.size();
            list.remove(pos);
        }
        return list.get(0);
    }
}

总结

经典的淘汰算法，环形运算锻炼脑子