题解 | #环形链表的约瑟夫问题#

题目：环形链表的约瑟夫问题

描述：编号为1到n的n个人围成一圈。从编号为1的人开始报数，报到m的人离开。下一个人继续从1开始报数。n−1轮结束以后，只剩下一个人，问最后留下的这个人编号是多少？

示例1：输入：5,2，返回值：3

说明：开始5个人1，2，3，4，5，从1开始报数，1->1，2->2编号为2的人离开

1，3，4，5，从3开始报数，3->1，4->2编号为4的人离开

1，3，5，从5开始报数，5->1，1->2编号为1的人离开

3，5，从3开始报数，3->1，5->2编号为5的人离开

最后留下人的编号是3

解法一：

举例分析+思路分析：约瑟夫环是一个经典的数学问题，如果我们按照规律进行依次报数的话会发现有一个递推公式，下面，我们使用表格进行解释，假设有5个人，第2个人会离开
图片说明
经过第一次，发现数字2离开了，剩余的人数变为4

第二次循环，数字4离开了，剩余的人数变为3

第三次循环，数字1离开了，剩余的人数变为2

最后一次，数字5离开了，剩余的人数变为1

最终留下的人的编号为3。

我们得到一个大致的递推公式为： $f(N,M)=(f(N−1,M)+M)%N$ ， $f(N,M)$ 表示N个人中第M个离开， $f(N-1,M)$ 表示N-1个人中第M个离开，根据上表，我们可以得到一个大致的逻辑就是，当有两个人的时候，没有离开的人的序号为0（假设序号是从0开始的），当有三个人的时候，没有离开的人的序号为2，当有四个人的时候，没有离开的人的序号为0……以此类推，便可以通过公式法将最终的结果反推出来，具体公式为 $res = (res + m) % i$ ，res的初始值为0。由此可以直接编写代码。

C++核心代码为：

class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @param m int整型 
     * @return int整型
     */
    int ysf(int n, int m) {
        // write code here
        int res = 0;
        for(int i = 2;i <= n;i++){
            res = (res + m) % i;//从2 开始进行推导
        }
        return res + 1;
    }
};

该方法直接采用数学公式法进行推导，所以时间复杂度为 $O(N)$ ，没有用到额外的内存空间，空间复杂度为 $O(1)$ 。

解法二：

思路分析：我们也可以建立一个单链表对象，首先将所有的值都添加到单链表当中，其次可以不断的判断单链表的大小值，通过设定一个index对象，刚开始赋值为0，只要 $index + m - 1$ 对单链表大小进行不断取余，然后删除，就可以找到最后一个值的位置。

实例分析：
图片说明
首先令 $index = 0$ ， $index = (index + m - 1) % res.size()$ ;，根据判断出局第一个元素为2，序号为1。

其次出局的元素为4，序号为3。

然后出局的元素为1，序号为0。

最后出局的元素为5，序号为4。

java核心程序为：

import java.util.*;
public class Solution {
    /**
     * 
     * @param n int整型
     * @param m int整型
     * @return int整型
     */
    public int ysf (int n, int m) {
        // write code here
        ArrayList<Integer> res = new ArrayList<>();
        for(int i = 1;i <= n;i++){
            res.add(i);//将n个人添加到链表中
        }
        int index = 0;
        while(res.size() > 1){
            index = (index + m - 1) % res.size();//判断删除的链表结点
            res.remove(index);//删除
        }
        return res.get(0);
    }
};

该算法需要遍历所有的元素，所以时间复杂度为 $O(N)$ ，需要新建一个单链表对象，用于存放元素结点，所以其空间复杂度为 $O(N)$ 。