环形链表的约瑟夫问题

#include <iostream>
#include <vector>
using namespace std;
int m, n;
struct node {
    int val;
    node* next;
};
node* fun(node* head, int m) {
    if (head == nullptr || head->next == head || m < 1)
        return head;
    node* last = head;
    while (last->next != head)
        last = last->next;
    int cnt = 0;
    while (head != last) {
        if (++cnt == m) {
            last->next = head->next;
            cnt = 0;
        }
        else {
            last = last->next;
        }
        head = last->next;
    }
    return head;
}


int main() {
    cin >> n >> m;
    node* head = nullptr;
    node* p = nullptr;
    for (int i = 1; i <= n; i++) {
        if (head == nullptr) {
            head = new node;
            head->val = i;
            head->next = nullptr;
            p = head;
            continue;
        }
        p->next = new node;
        p = p->next;
        p->val = i;
        p->next = nullptr;
    }
    p->next = head;
    node* node1 = fun(head, m);
    cout << node1->val << endl;
    system("pause");
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, m, s=0;
    scanf("%d%d", &n, &m);
    for(int i=2;i<=n;i++)
        s = (s+m)%i;
    printf("%d\n", s+1);
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,m,res=0;
    cin>>n>>m;
    for(int i = 2; i <= n; i++)
        res = (res + m)%i;
    cout<<(res + 1);
    return 0;
}

/*简单模拟*/
#include <stdio.h>
#include <stdlib.h>

typedef struct nd {
    int val;
    struct nd *next;
} node;

node *create_node(int val) {
    node *n = (node *) malloc(sizeof(node));
    n->val = val;
    n->next = NULL;
    return n;
}

node *josephus_kill(node *head, int m) {
    int tmp = 1;
    node *pre, *cur = head;
    while (cur->next != head)
        cur = cur->next;
    pre = cur;
    cur = head;
    while (cur->next != cur) {
        if (tmp == m) {
            tmp = 1;
            pre->next = cur->next;
            free(cur);
            cur = pre->next;
            continue;
        }
        pre = cur;
        cur = cur->next;
        tmp++;
    }
    return cur;
}

int main(void) {
    int n, m;
    scanf("%d%d", &n, &m);
    
    node dh = {0, NULL}, *cur = &dh;
    for (int i = 0; i < n; i++) {
        cur->next = create_node(i + 1);
        cur = cur->next;
    }
    cur->next = dh.next;
    cur = josephus_kill(dh.next, m);
    printf("%d\n", cur->val);
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, m;
    cin >> n >> m;
    int alive = 0;
    for(int i = 2; i <= n; i++){
        alive = (alive + m)%i;
    }
    cout << alive+1 <<endl;
    return 0;
}

import java.util.*;
class node{
        int val;
        node next;
        public node(){};
        public node(int val) {
            this.val = val;
        }
}

public class Code61_yuesefuProblem {
    public static void main(String[] args) {
        node ans = new node();
        node index = ans;
        Scanner in = new Scanner(System.in);
        node mynode = new node();
        int n = in.nextInt();
         int m=in.nextInt();
        for (int i = 1; i <= n; i++) {
            node temp = new node(i);
            index.next = temp;
            index = index.next;
        }
        index.next = ans;
        int ch=n;
        int count=1;
        node p=ans;
        node q=ans.next;
        while(ch!=1) {
            if (count == m &&q.val!=0) {
                //System.out.println("所删除的节点"+q.val);
                q = q.next;
                p.next = q;
                count = 1;
                ch--;
            } else if (count != m &&q.val!=0) {
                p = p.next;
                q = q.next;
                count++;
            }
            else{
                p=p.next;
                q=q.next;
            }
        }
        node test=ans.next;
        while(true) {
            if(test.val!=0){
                System.out.println(test.val);
                break;
            }
            test=test.next;
        }
            }
        }


大概思路
1.就是循环赋值然后附完值后让指针指向头形成单循环链表
2.然后删除用的基本操作遇到对应的删除节点时前指针先走一步然后后指针指向他删除该指针并且计数器count置为1,如果不是的话就俩指针各走一步然后count++
3.对了我加了一个q.val!=0是因为我创建的链表是带头节点的方便操作但是头节点不参与循环所以到他的时候基数器不参与任何变化

n,m=map(int,input().split())
l=list(range(1,n+1))
res=0
#模拟删除过程
#每次去掉一个人
#相当于i+1
for i in range(1,n+1):
    res=(res+m)%i
print(res+1)

import java.util.*;

public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        //初始化队列
        Queue<Integer> queue = new LinkedList<>();
        //向队列中添加元素
        for (int i=1; i<=n; i++){
            queue.offer(i);
        }
        //判断队列的元素是否为1
        while (queue.size() != 1){
            //向队列尾部添加队列前m-1个元素，同时删除队列前m-1个元素
            for (int i=1; i<m; i++){
                queue.offer(queue.poll());
            }
            //删除队列第m个元素
            queue.poll();
        }
        //如果队列只有1个元素，输出元素，不删除队列元素
        System.out.println(queue.peek());
    }
}