环形链表的约瑟夫问题

思路：

1.先创建编号为1的人的节点作为循环链表的头结点

2.将剩下的所有的人创建对应的节点连接形成形成链表

3.将链表的首尾相连，因为对于约瑟夫问题，需要的是循环链表

4.进行游戏，每次让第m个人出圈

代码：

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param m int整型 
     * @return int整型
     */
    public int ysf (int n, int m) {
        //创建一个头结点，表示编号为1的人的节点
        ListNode head=new ListNode(1);
        ListNode temp=head;
        ListNode p;
        //创建剩下编号的人的节点，连成链表
        for(int i=2;i<=n;i++){
            p=new ListNode(i);
            temp.next=p;
            temp=temp.next;
        }
        //由于对于约瑟夫问题，需要的是一个首尾相连的循环的链表
        temp.next=head;
        //创建一个pre指针用来保存需要删除的节点的前一个节点
        //用cur用来保存需要删除的节点的位置
        ListNode pre=head;
        ListNode cur=head;
        //只要链表中还有大于一个人，就继续游戏
        while((n--)>1){
            //对于每一轮游戏，都进行m-1次循环，定位pre和cur的位置
            for(int i=1;i<m;i++){
               pre=cur;
               cur=cur.next;
            }
            //将数到m的人的节点进行删除
            pre.next=cur.next;
            //更新下一次数数的人的编号
            cur=pre.next;
        }
        //返回最后一个未出圈的人的编号
        return cur.val;



    }
}