约瑟夫环Java实现
约瑟夫环描述：编号为0到n-1的n个人围成一圈。从编号为0的人开始报数1，依次下去，报到m的人离开，问最后留下的一个人，编号是多少？
输出描述: 输出最后一个留下来的人的编号
思路一：写一个单向循环链表。每m个就删除一个节点。如果链表中只剩下来最后，那么答案就是它了。
思路一：写一个单向循环链表。每m个就删除一个节点。如果链表中只剩下来最后，那么答案就是它了。
1 构建一个单向循环链表，每一个节点的值是其报数的数字，从1开始。
2 构建一个虚拟头节点，从头结点开始，每m个开始删除。
具体的删除逻辑是使用pre指针来删除。
3 当链表只剩下最后一个，就可以返回该值了
import java.util.*;
public class Solution {
/**
*
* @param n int整型
* @param m int整型
* @return int整型
*/
public int ysf (int n, int m) {
// write code here
Node head = new Node(-1); // 虚拟头节点
Node cur = head;
for (int i = 1; i <= n; i++){ // 把所有报数都放进链表中
Node node = new Node(i);
cur.next = node;
cur = cur.next;
}
cur.next = head.next; // 单向循环链表
cur = head; // cur指针重新回来头部
Node pre = null;
while (cur.next != null){
int count = m; // 注意这里每一次都需要更新为m
while (count-- > 0){
pre = cur;
cur = cur.next;
}
// 删除这个节点
pre.next = cur.next;
cur.next = null;
cur = pre;
}
return cur.val;
}
}
class Node{
int val;
Node next;
Node() {};
Node(int num) {
this.val = num;
}
} 思路二：使用数组的方法解决 1 将所有的报数都放在一个容器中
2 每一个使用取出下标来删除 (cur + m - 1) 表示要取出来的元素， % len 是为了防止数组溢出 （这个 % len是解这道题的关键）
3 返回最后一个数。
public class Solution {
* @param n int整型
* @param m int整型
* @return int整型
*/
public int ysf (int n, int m) {
// write code here
List<Integer> list = new ArrayList<>();
for (int i = 1; i <= n; i++){
list.add(i);
}
int cur = 0;
while (list.size() > 1){ // 删到只剩下一个元素
int len = list.size();
cur = (cur + m - 1) % len;
list.remove(cur);
}
return list.get(0);
}
} 
查看5道真题和解析