前言

以专题的形式更新刷题贴，欢迎跟我一起学习刷题，相信我，你的坚持，绝对会有意想不到的收获。每道题会提供简单的解答，如果你有更优雅的做法，欢迎提供指点，谢谢

【题目描述】
【要求】

输入：一个环形单向链表的头节点 head 和报数 m.

返回：最后生存下来的节点，且这个节点自己组成环形单向链表，其他节点都删除掉。

【难度】

士：★☆☆☆

【解答】

方法1：时间复杂度为 O( n * m)

这道题如果不考虑时间复杂度的话还是挺简单的，就遍历环形链表，每遍历 m 个节点就删除一个节点，知道链表只剩下一个节点就可以了。

代码如下

1//时间复杂度为O(n*m)的解决方法
2publicstaticNodejosephusKill(Nodehead,intm){
3if(head==null||m<1)
4returnhead;
5Nodelast=head;
6//定位到最后一个节点
7while(head.next!=last){
8head=head.next;
9}
10intcount=0;
11while(head.next!=head){
12if(++count==m){
13head.next=head.next.next;
14count=0;
15}else{
16head=head.next;
17}
18}
19returnhead;
20}

由于有些手机可能会出现乱码问题，我这里再贴出图片：

这个方法的时间复杂度为 O(n * m)。下面用时间复杂度为方法解决。

方法二：时间复杂度为 O(n)

这个方法的难度为：

校：★★★☆

我们可以给环形链表的节点编号，如果链表的节点数为 n, 则从头节点开始，依次给节点编号，即头节点为 1， 下一个节点为2， 最后一个节点为 n.

我们用 f(n) 表示当环形链表的长度为n时，生存下来的人的编号为 f(n)，显然当 n = 1 时，f(n) = 1。假如我们能够找出 f(n) 和 f(n-1) 之间的关系的话，我们我们就可以用递归的方式来解决了。我们假设 人员数为 n, 报数到 m 的人就自杀。则刚开始的编号为

…

m - 2

m - 1

m

m + 1

m + 2

…

进行了一次删除之后，删除了编号为m的节点。删除之后，就只剩下 n - 1 个节点了，删除前和删除之后的编号转换关系为：

删除前 --- 删除后

… --- …

m - 2 --- n - 2

m - 1 --- n - 1

m ----无(因为编号被删除了)

m + 1 --- 1(因为下次就从这里报数了)

m + 2 ---- 2

… ---- …

新的环中只有 n - 1 个节点。且编号为 m + 1, m + 2, m + 3 的节点成了新环中编号为 1， 2， 3 的节点。

假设 old 为删除之前的节点编号， new 为删除了一个节点之后的编号，则 old 与 new 之间的关系为 old = (new + m - 1) % n + 1。

注：有些人可能会疑惑为什么不是 old = (new + m ) % n 呢？主要是因为编号是从 1 开始的，而不是从 0 开始的。如果 new + m == n的话，会导致最后的计算结果为 old = 0。所以 old = (new + m - 1) % n + 1.

这样，我们就得出 f(n) 与 f(n - 1)之间的关系了，而 f(1) = 1.所以我们可以采用递归的方式来做。

代码如下：

1//时间复杂度为O(n)
2publicstaticNodejosephusKill2(Nodehead,intm){
3if(head==null||m<1)
4returnhead;
5intn=1;//统计一共有多少个节点
6Nodelast=head;
7while(last.next!=head){
8n++;
9last=last.next;
10}
11//直接用递归算出目的编号
12intdes=f(n,m);
13//把目的节点取出来
14while(--des!=0){
15head=head.next;
16}
17head.next=head;
18returnhead;
19}
20
21privatestaticintf(intn,intm){
22if(n==1){
23return1;
24}
25return(f(n-1,m)+m-1)%n+1;
26}
图片代码：

问题拓展

对于上道题，假设是从第 K 个节点开始报数删除呢？ 又该如何解决呢？