首先先了解一下什么是约瑟夫环问题

据说著名犹太历史学家Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。问题是，给定了和，一开始要站在什么地方才能避免被处决。Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。
对于此问题用单链表实现再好不过了，当单链表首尾相接时就成了一个环：
自杀的操作可以理解为节点被删除；
代码实现：

#include<iostream>
using namespace std;
typedef struct ListNode{
	int data;
	struct ListNode *next;
}SlistNode,*PListNode;
PListNode creatList(int n){
	PListNode head;
	PListNode rear;
	PListNode temp;
	head=rear=NULL;
	for(int i=0;i<n;i++){
		temp=new SlistNode;
		temp->data=i+1;
		if(head==NULL)
			head=temp;
		else
			rear->next=temp;
		rear=temp;
	}
	 if(rear!=NULL) rear->next=NULL; // 末尾结点指针域置为NULL
	    return head; 
}
void show(PListNode head){
	PListNode p=head;
	while(p!=NULL){
		cout<<p->data<<" ";
		p=p->next;
	}
	cout<<endl;
}
PListNode JosephCircle(PListNode head,int x){
	int count=0;
	PListNode cur=head,tail=head;
	PListNode str;
	if(head==NULL){
		return NULL;
	}
	while(tail->next!=NULL)
		tail=tail->next;
	tail->next=head;//将链表首尾相连
	while(cur->next!=cur){
		count=x;
		while(--count){
			cur=cur->next;
		}	
		//cur为待删除节点，可以采用替换法删除，str的值赋值给cur，删除str
		cout<<cur->data<<" ";
		str=cur->next;
		cur->data=str->data;
		cur->next=str->next;
		delete str;
	}
	return cur;
}
int main(){
	PListNode head=creatList(41);
	PListNode live=JosephCircle(head,3);
	cout<<live->data<<endl;
	return 0;
}

当人数为41时，可以看到出局顺序为