环形单链表的约瑟夫（Josephus）问题

题目

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

输入：一个环形单向链表的头节点 head 和报数的值 m。
返回：最后生存下来的节点

进阶问题：如果链表节点数为 $N$，想在时间复杂度为 $O(N)$ 时完成原问题的要求，该怎么实现？

解答

方法一

直接模拟，这个按部就班写代码即可。

代码

public class Node {
    public int value;
    public Node next;

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

/**
 * 直接法模拟约瑟夫环的删除过程
 * @param head 环形单向链表的头节点
 * @param m 每隔 m 个节点删除一次
 * @return 最后的幸存者
 */
public Node josephusKill(Node head, int m) {
    if (head == null || head.next == head || m < 1) { // 输入不合理
        return head;
    }
    Node last = head;
    // 找出最后一个节点 last
    while (last.next != head) {
        last = last.next;
    }
    int count = 0;
    while (head != last) {
        if (++count == m) { // 如果报数到了 m
            last.next = head.next; // 删除节点
            count = 0; // count 重又归零
        } else {
            last = last.next; // last 往后移动一位
        }
        head = last.next; // 移动 head 指针，使 head 指针始终保持是 last 指针的下一位
    }
    return head;
}

方法一的时间复杂度为 $O(N \times m)$，$N$ 是节点数。

方法二

公式法。通过找规律，直接利用递推公式来求解。注意，这个公式法并不是书上介绍的方法，而是上个学期在上数据结构课程时老师讲述的方法。具体思路如下。

首先，我们给出公式

J(n, m) = J(J(n - 1, m) + m) % n, if n > 1,
J(1, m) = 0

下面，我们就来简单证明一下这个算法。

举例，我们用数字表示每一个人：

$$1,2,3,4,5,6,7,8,9,10,11$$

一共 11 个人，他们排成一排，假设报到 3 的人被杀掉。

• 刚开始时，头一个人编号是1，从他开始报数，第一轮被杀掉的是编号3的人。
• 编号4的人从1开始重新报数，这时候我们可以认为编号4这个人是队伍的头。第二轮被杀掉的是编号6的人。
• 编号7的人开始重新报数，这时候我们可以认为编号7这个人是队伍的头。第三轮被杀掉的是编号9的人。
• ……
• 第九轮时，编号2的人开始重新报数，这时候我们可以认为编号2这个人是队伍的头。这轮被杀掉的是编号8的人。
• 下一个人还是编号为2的人，他从1开始报数，不幸的是他在这轮被杀掉了。
• 最后的胜利者是编号为7的人。

表格演示(表头代表数组的下标)：

0	1	2	3	4	5	6	7	8	9	10
1	2	3	4	5	6	7	8	9	10	11
4	5	6	7	8	9	10	11	1	2
7	8	9	10	11	1	2	4	5
10	11	1	2	4	5	7	8
2	4	5	7	8	10	11
7	8	10	11	2	4
11	2	4	7	8
7	8	11	2
2	7	8
2	7
7

我们用上面的数据验证一下公式的正确性，其中，J(n, m) 表示的是幸存者在这一轮的下标位置：

• $J(1, 3) = 0$；只有一个人，此人是最后的幸存者，其在数组中的下标为 0
• $J(2, 3) = 1 = (J(1, 3) + 3) % 2$；还剩 2 个人时
• $J(3, 3) = 1 = (J(2, 3) + 3) % 3$；还剩 3 个人时
• $J(4, 3) = 0 = (J(3, 3) + 3) % 4$
• $J(5, 3) = 3 = (J(4, 3) + 3) % 5$
• …
• $J(11, 3) = 6 = (J(10, 3) + 3) % 11$；最终计算出待求的情况

我们通过实例只是验证了这一种情况是成立的，这能够很好地辅助我们理解，但是，我们还需要这个公式的具体推导，下面，就以问答的方式来推导这个公式。

问题1：假设我们已经知道 11 个人时，幸存者的下标位置为 6，那么下一轮 10 个人时，幸存者下标的位置是多少？

答：我们在第 1 轮杀掉第 3 个人时，后面的人都往前面移动了 3 位，幸存者也往前移动了 3 位，所以他的下标由 6 变成了 3。

问题2：假设我们呢已经知道 10 个人时，幸存者的下标位置为 3，那么上一轮 11 个人时，幸存者下标的位置是多少？

答：这可以看成是上一个问题的逆过程，所以由 10 变成 11 个人时，所有人都往后移动 3 位，所以 $J(11, 3) = J(10, 3) + 3$，不过数组可能会越界，我们可以想象成数组的首尾是相接的环，那么越界的元素就要重新回到开头，所以这个式子还要模取当前的人数(注意，这里是当前数组，在这里就是人数为 11 的这个数组)：$J(11,3) = (J(10, 3) + 3) % 11$。

问题3：推及到一般情况，人数为 n，报到 m 时，把那个人杀掉，那么数组又是怎么移动的？

答：由上面的推导，我们应该很容易就能得出，若已知 n - 1 个人时，幸存者的下标位置为 $J(n - 1, m)$，那么 n 个人的时候，就是往后移动 m 位，同样的，因为可能数组越界，所以式子要变成：$J(n, m) = (J(n - 1, m) + 3) % n$。

代码

/**
 * 使用公式法求解最后幸存的节点
 * @param head 单向环状链表头节点
 * @param m 报数到 m 就删去一个节点
 * @return 最后生存的节点
 */
public Node JosephusKillFormula(Node head, int m) {
    int n = 0; // n 表示链表的长度
    Node last = head;
    while (last.next != head) {
        n++;
        last = last.next;
    }
    n++;
    int p = 0; // 只剩一个人时，数组下标为 0
    // 这个循环就是关键的核心
    for (int i = 2; i <= n; i++) {
        p = (p + m) % i; // i 是当前的人数
    }
    p += 1; // 因为 p 是从 0 开始，所以最后要加一
    while (--p != 0) {
        last = last.next;
        head = head.next;
    }
    last.next = null;
    head.next = null; // 只取最后的 head 这一个节点，其他都舍去
    return head;
}