约瑟夫环报数，直到剩下k-1人停止

题目

有n个囚犯围成一圈从1到n编号，并从1开始报数。每当报到k，这个囚犯就会被执行死刑。接着从下一个人开始，剩下的囚犯继续从1开始报数并重复这个过程。直到所有囚犯的数目加起来小于k。问给定n和k，初始站在什么位置的囚犯能活下来？（k > 1 && k <=n)。

Analysis

对于这道题目，首先我们应该明确当k输入非法的情况（既k<=1或k>n的情况，这两种情况下要么囚犯全部无法存活要么全部存活）。在这种情况下程序抛出异常以表示输入非法。

对于其余的情况，我们可以模拟整个循环报数的过程直到满足囚犯数目小于k为止。此时剩下的编号即为我们要求的编号。考虑到这种循环遍历且需要移除某个位置的元素的问题，LinkedList这种数据结构是比较适合的。因为我们在循环报数的过程中，一定是按顺序遍历的。所以只要利用LinkedList的next指针即可。同时考虑到移除当前元素后当前元素的前一个元素的next指针需要指向当前元素的后面一个元素，使用DoubleLinkedList能够大大简化这一过程的实现。同时考虑到这些囚犯是围成一个环，所以我们需要让链表的头尾相连形成一个环状链表。

事实上不使用循环链表而使用Queue的FIFO特性也可以实现这一模拟的过程。

时间复杂度

考虑到我们需要不断循环整个链表，且每报k个数杀掉一个囚犯，且由于使用了双向链表，移除一个元素的时间为O(1)。因此每移除一个元素需要的时间为k*O(1)=O(k)。要循环到整个链表只剩k-1个元素，即删除了n-（k-1)个元素，那么总时间复杂度为O(k)*(n-k+1)=O(nk)。

实现如下：

public class JosephProblem {
    private static class Node {
        Node next;
        Node prev;
        int val;
        
        Node(int val) {
            this.val = val;
        }
    }
    public static List<Integer> josephSurviver(int n, int k) throws IllegalArgumentException {
        if (k <= 1 || k > n) {
            throw new IllegalArgumentException("k out of boundary!");
        }
        
        int size = n; 
        Node head = new Node(1);
        Node curr = head;
        for (int i = 1; i < n; i++) {
            curr.next = new Node(i + 1);
            curr.next.prev = curr;
            curr = curr.next;
        }
        // make the LinkedList a circle
        curr.next = head;
        head.prev = curr;
        curr = head;
        
        while (size >= k) {
            // Count off
            for (int i = 1; i <= k - 1; i++) {
                curr = curr.next;
            }
            
            // Remove the kth element
            curr.prev.next = curr.next;
            curr.next.prev = curr.prev;
            size--;
            
            // Start from next person next time.
            curr = curr.next;
        }
        
        List<Integer> ret = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            ret.add(curr.val);
            curr = curr.next;
        }
        
        return ret;
    }
}