问题描述：

约瑟夫环是一个数学的应用问题：已知n个人（以编号1，2，3…n分别表示）围坐在一张圆桌周围。由第一个人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到最后剩下一个人。

一般的思路就是通过一个count计数的方法，循环遍历链表，逐一删除。但是这样的方法时间复杂度要有O（n×m），（总共要删除n-1个数，每删除一个需要遍历m次）。那有没有什么办法直接就找到我们需要删除的那个节点呢，比如给你链表1→2→3→4→5→1，这是环状链表。如果m=3的话，最后留下的是第4个节点。这里我们就需要借用数学的方式来进行推到公式，利用递归的方式求解了。

递归求解思路：

（我通过递归的方式，返回需要删除第几个节点，所以，节点编号从1开始，返回的也是第几个节点）

第一次删除第m个节点很简单，就是m%n的那个节点，但是第二次删除节点就有点困难了，为什么，因为，你需要从第m+1的节点重新从1开始数，数到第m个节点再次删除。其实，不知道你们有没有发现，其实第二次开始数的第1个节点，就是上一次的m+1号节点。所以前一个链表节点和后一个链表节点对应的编号关系就是：

oldNum=（newNum+m-1）%（当前节点数）+1 （1）

下面从图片分析下：

根据公式（1）的关系，你就可以由新链表找到对应就链表的编号位子了。当链表中由i个节点时，编号对应的公式是：num(i) = （num（i-1）+m-1）%i +1;

（如果链表从0开始编号的话，那么公式就是num(i) = （num（i-1）+m）%i ），返回的是下标值，且最后num（1） = 0；）

代码实现：

public class JosephusProblem {   //链表节点类    public static class Node {        public int value;        public Node next;        public Node(int data) {            this.value = data;        }    }    public static Node josephusKill2(Node head, int m) {        if (head == null || head.next == head || m < 1) {            return head;        }        Node cur = head.next;        int tmp = 1; // 表示链表长度        /*        *计算链表长度        */        while (cur != head) {            tmp++;            cur = cur.next;        }        tmp = getLive(tmp, m); // 返回链表中应该删除的那个值位置        while (--tmp != 0) {            head = head.next;        }        head.next = head;        return head;    }    public static int getLive(int i, int m) {        if (i == 1) {        //如果从0开始编号的话，此处return 0            return 1;        }        //如果从0开始编号的话，此处(getLive(i - 1, m) + m) % i，返回的就是下标值，比如从1开始，返回的是4，而从0开始，返回的是3        return (getLive(i - 1, m) + m - 1) % i + 1;//这个就是上述公式实现    }}

参考文献：