单向循环链表求约瑟夫代码

以下是单向循环链表求约瑟夫问题的代码实现：

#include <iostream>
using namespace std;
 
// 定义单向循环链表节点
struct Node {
    int data; // 数据域
    Node* next; // 指针域
    Node(int val = 0) : data(val), next(nullptr) {} // 构造函数
};
 
// 定义单向循环链表类
class CirLinkedList {
public:
    CirLinkedList(); // 构造函数
    ~CirLinkedList(); // 析构函数
    void CreateList(int n); // 创建长度为n的单向循环链表
    void Josephus(int m); // 约瑟夫问题，每m个节点删掉一个
private:
    Node* first; // 链表头指针
};
 
CirLinkedList::CirLinkedList() {
    first = nullptr; // 初始化链表为空
}
 
CirLinkedList::~CirLinkedList() {
    // 释放链表内存
    Node* temp = first;
    while (temp) {
        Node* p = temp;
        temp = temp -> next;
        delete p;
    }
}
 
void CirLinkedList::CreateList(int n) {
    if (n < 1) return;
 
    first = new Node(1); // 创建第一个节点
    Node* temp = first;
    // 创建剩余的n-1个节点
    for (int i = 2; i <= n; ++i) {
        Node* p = new Node(i);
        temp -> next = p;
        temp = temp -> next;
    }
    temp -> next = first; // 最后一个节点指向头结点，形成单向循环链表
}
 
void CirLinkedList::Josephus(int m) {
    // 如果链表为空，直接退出
    if (first == nullptr) return;
 
    Node* pre = nullptr; // pre指向待删除节点的前一个节点
    Node* cur = first; // cur指向待删除节点
    // 找到待删除节点，确保链表中至少有两个节点
    while (cur -> next != cur) {
        // 移动m-1步，找到待删除节点
        for (int i = 0; i < m - 1; ++i) {
            pre = cur;
            cur = cur -> next;
        }
        pre -> next = cur -> next; // 将待删除节点从链表中删除
        cout << cur -> data << " "; // 输出删除的节点
        delete cur; // 释放删除的节点内存
        cur = pre -> next; // 更新待删除节点为下一个节点
    }
    // 输出链表剩余节点
    cout << cur -> data << endl;
}
 
int main() {
    int n, m;
    cin >> n >> m; // 输入链表长度n和每次删掉的节点数m
    CirLinkedList cll;
    cll.CreateList(n); // 创建单向循环链表
    cll.Josephus(m); // 解决约瑟夫问题
    return 0;
}