题目
有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;
}
}
