约瑟夫环问题 java

约瑟夫环问题是一个经典的问题，其描述为：已知 n 个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为 k 的人开始报数，数到 m 的那个人出列；他的下一个人又从 1 开始报数，数到 m 的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。根据传统，约瑟夫问题的参数通常以(n,m,k)表示，一般化后的问题可以表述为：已知 n 个人围坐在一张圆桌周围，并从编号为 k 的人开始报数，数到第 m 个数的人出列，如此重复，直到圆桌周围的人全部出列。求解约瑟夫问题就是要求出出列的顺序。

以下是 Java 中使用循环链表解决约瑟夫环问题的代码：

public static void main(String[] args) {
    int n = 5, k = 3, m = 2;
    Node head = new Node(1);
    Node p = head;
    for (int i = 2; i <= n; i++) {
        p.next = new Node(i);
        p = p.next;
    }
    p.next = head;
    while (p != p.next) {
        for (int i = 1; i < k; i++) {
            p = p.next;
        }
        for (int i = 1; i < m - 1; i++) {
            p = p.next;
        }
        System.out.print(p.next.value + " ");
        p.next = p.next.next;
    }
    System.out.println(p.value);
}

static class Node {
    int value;
    Node next;

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

运行结果为：3 5 2 4 1