【刷题】牛客网 NC132 环形链表的约瑟夫问题

typedef struct listnode{
    int val ;
    struct listnode* next;
} Listnode;

Listnode* buynode(int n ){
	//开辟空间
    Listnode* node = (Listnode*)malloc(sizeof(Listnode));
    //序号赋值
    node->val = n;
    //next 指针赋值
    node->next = NULL;
    //返回节点
    return node;
}
 Listnode* createlist(int n){
    //序号
    int i = 1;
    //创建头尾
    Listnode* phead ,*ptail;
    //先创建第一个节点
    phead = ptail = buynode(i++);
    //循环构建链表
    while(i<=n){
        ptail->next = buynode(i++);
        ptail = ptail->next;
    }
	//将头尾相连，构成循环链表
    ptail->next = phead;
    //返回头节点
    return phead;

 }
int ysf(int n, int m ) {
    // 创建环形链表
    Listnode * head = createlist(n);

    //约瑟夫问题
    //计数
    int count = 1 ;
    //定义 前指针 当前指针
    Listnode* cur ,*prev;
    cur = head;
    prev = NULL;
    while(cur->next != cur){
    	//报到指定数 删除节点
        if(count == m){
        	//前节点 的next指向 当前节点的下一个节点即可删除
            prev->next = cur->next;
            cur = cur->next;
            //报数重置
            count = 1;

        }else{
        	//没有报到指定数 则向后移动。
            prev = cur;
            cur = cur->next;
            count++;
        }
    }
   	//返回序号
    return cur->val;
}

#define max_num 100001
int ysf(int n, int m ) {
    //初始化数组
    int man[100001];
    for(int i = 0;i<n;i++){
        man[i] = i + 1;
    }
    //计数
    int count = 1;
    //控制下标
    int i =0;
    while(n > 1 ){
        //如果报到对应数
        if(count == m){
        //向前覆盖删除元素
            for(int j = i;j < n-1;j++){
                man[j] = man[j + 1];
            }
            //计数重置
            count = 1;
            //人数减 1
            n--;
            //注意不需要将 i++ 因为删除过程 i 已经指向了后一个元素。
        }
        else{
        //不是对应数 i++ 计数加1
            i++;
            count++;
        }
		//保证不超出 n 范围
        i %= n;

    }
    //返回对应序号
    return man[i];
}

int ysf(int n, int m ) {
    //F（N，M）=（F（N-1，M）+M）%N
    //最后幸存者下标为 0
    int p = 0;
    //从人数为2开始逆推，直到人数为n
    for (int i = 2; i <= n; i++) {
    	//依次移动
        p = (p + m) % i;
    }
    //记得将序号加一
    return p + 1;

}