Java采用循环链表结构求解约瑟夫问题

什么是约瑟夫问题

约瑟夫问题（Josephus problem）是一个著名的趣题，其描述如下：
$n$ 个人围成一圈，从第 $1$ 个人开始报数，报到第 $m$ 个人出圈，然后从出圈的下一个人开始重新报数，重复这个过程，直到圈中只剩下最后一个人，求出这个人的编号。

解决方式

约瑟夫问题的求解方式很多，这里介绍一种使用循环链表结构的方式。主要思路是将 $n$ 个人顺序地组成一个循环链表，每次删除第 $m$ 个人，直至只剩一个人。以下是详细步骤。

1. 定义节点类
   首先，我们需要定义一个节点类，用于表示每个人。这个节点类应该包含两个属性：编号 $num$ 和指向下一个节点的引用变量 $next$。

public class Node {
    public int num; // 编号
    public Node next; // 下一个节点的引用

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

1. 构建循环链表
   我们将 $n$ 个人按顺序加入循环链表中，最后一个人的 $next$ 引用指向第一个人，形成一个闭环。

public Node buildCircularList(int n) {
    if (n < 1) {
        throw new IllegalArgumentException("n 必须大于等于 1");
    }
    Node head = new Node(1);
    Node tail = head;
    for (int i = 2; i <= n; i++) {
        Node node = new Node(i);
        tail.next = node;
        tail = node;
    }
    tail.next = head;
    return head;
}

1. 删除节点
   删除第 $m$ 个节点，可以通过一个循环来实现。每次遍历到第 $m$ 个节点时，删除该节点，并更新上一个节点的 $next$ 引用。

public Node deleteNode(Node head, int m) {
    if (head == null || m < 1) {
        return null;
    }
    int count = 1;
    Node prev = null;
    Node cur = head;
    while (cur.next != cur) {
        if (count == m) {
            // 删除节点
            prev.next = cur.next;
            cur.next = null;
            // 打印删除的节点编号
            System.out.print(cur.num + " ");
            // 移动到下一个节点
            cur = prev.next;
            count = 1;
        } else {
            prev = cur;
            cur = cur.next;
            count++;
        }
    }
    return cur;
}

1. 示例
   比如，现有 $n=7$ 个人，从第一个人开始报数，数到 $m=3$ 的人出圈。则循环链表构建完成后的样子为：

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 1 -> ...

按照删除节点的规则，依次删除第 3、6、2、7、5、1 号节点。直到最后只剩下第 4 号节点。

public static void main(String[] args) {
    int n = 7;
    int m = 3;

    // 构建循环链表
    Node head = new JosephusProblem().buildCircularList(n);

    // 删除节点
    System.out.print("删除节点顺序：");
    Node lastNode = new JosephusProblem().deleteNode(head, m);
    System.out.println("\n剩余节点编号：" + lastNode.num);
}

输出结果为：

删除节点顺序：3 6 2 7 5 1 
剩余节点编号：4

因此，最后留存的节点编号为 4，即第 4 个人。同理，也可以按照此思路求解其他情况下的约瑟夫问题。