【C/C++】循环链表实现约瑟夫问题

#include <iostream>
using namespace std;
typedef struct node {
  int data;
  node* next;
  node() :data(0), next(nullptr) {}
  node(int x) :data(x), next(nullptr) {}
}node;

//循环链表实现约瑟夫问题
void ysflb(int n, int k) {
  if (n <= 0 || k <= 0) {
    cout << "Invalid input: n and k must be positive integers." << endl;
    return;
  }

  // 创建循环链表  
  node* head = new node;
  if (!head) {
    cout << "Memory Failed!\n";
    return;
  }
  head->data = 1; // 第一个人的编号从1开始  
  node* p = head;

  // 赋值  
  for (int i = 2; i <= n; i++) {
    node* r = new node;
    r->data = i;
    r->next = NULL;
    p->next = r;
    p = r;
  }
  p->next = head; // 形成循环链表  

  // 约瑟夫环的模拟  
  node* prev = NULL;
  node* curr = head;
  while (curr->next != curr) { // 当链表中不止一个节点时  
    for (int i = 1; i < k; i++) {
      prev = curr;
      curr = curr->next;
    }
    cout << curr->data << " "; // 输出出局者的编号  
    prev->next = curr->next; // 删除当前节点  
    node* tmp = curr;
    curr = curr->next;
    delete tmp; // 释放当前节点的内存  
  }
  cout << curr->data << endl; // 输出最后一个出局者的编号  
  delete curr; // 释放最后一个节点的内存  
}

int main(void) {
  ysflb(10, 3);
  return 0;
}