环形单链表的约瑟夫问题

【题目】 据说著名犹太历史学家 Josephus 有过以下故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus 及他的朋友躲到一个洞中，39 个犹太人决定宁愿死也不要被敌人抓到，于是决定了一种自杀方式，41 个人排成一个圆圈，由第 1 个人开始报数，报数到 3 的人就自杀，然后再由下一个人重新报 1，报数到 3 的人再自杀，这样依次下去，直到剩下最后一个人时，那个人可以自由选择自己的命运。这就是著名的约瑟夫问题。现在请用单向环形链表描述该结构并呈现整个自杀过程。 输入：一个环形单向链表的头节点 head 和报数的值 m。 返回：最后生存下来的节点，且这个节点自己组成环形单向链表，其他节点都删掉。 进阶问题：如果链表节点数为 N，想在时间复杂度为 O(N)时完成原问题的要求，该怎么实现？

【解答】 先来看看普通解法是如何实现的，其实非常简单，方法如下： 1．如果链表为空或者链表节点数为 1，或者 m 的值小于 1，则不用调整就直接返回。 2．在环形链表中遍历每个节点，不断转圈，不断让每个节点报数。 3．当报数到达 m 时，就删除当前报数的节点。 4．删除节点后，别忘了还要把剩下的节点继续连成环状，继续转圈报数，继续删除。 5．不停地删除，直到环形链表中只剩一个节点，过程结束。 普通的解法就像题目描述的过程一样，具体实现请参看如下代码中的 josephusKill1 方法。

public class JosephusKill1 {

    class Node {
        private int value;
        private Node next;
        public Node(int data) {
            this.value = data;
        }
    }

    public Node josephusKill1(Node head, int m) {
        if (head == null || head.next == null || m < 1) {
            return head;
        }

        Node last = head;
        // 先找出链表的尾节点，循环结束时，last指向链表的尾节点
        while (last.next != head) { // O(N)
            last = last.next;
        }

        int count = 0;
        // 循环中使last节点在前，head节点在后，head节点是报数的那个人
        // 如果last节点和head节点相等，就表明环形单链表中只剩一个节点
        while (last != head) { // O(m*N)
            // 数到数等于m使，杀掉一个人
            if (++count == m) {
                // last节点的next指针指向head节点的后一个节点，就等于把head杀掉了
                last.next = head.next;
                count = 0;
            } else {
                // 如果count不等于m，last节点向后移
                last = last.next;
            }
            // head节点也向后移动，新一个人开始报数
            head = last.next;
        }
        // 返回活下来的那个人
        return head;
    }
}

这种解法每删除一个节点，都需要遍历 m 次，一共需要删除的节点数为 n-1，所以普通解法的时间复杂度为 O(n×m)。