双向链表 约瑟夫合并（C++）_双向链表的合并算法

#include<iostream>
using namespace std;
class dnode{//定义节点 
	public:
		int nodeValue;//该节点的值 
		dnode *prev;//连接前后两个节点 
		dnode *next;
		dnode(){
			next=this;
			prev=this;
		}
		dnode(const int &value):nodeValue(value){
			next=this;
			prev=this;
		}
};
class myList{
	private:
		dnode *first;
		int size;
	public:
	void push_back(int data);
	void pop_back();
	void push_front(int data);
	void pop_front();
	void insert(int pos,int data);
	void erase(int pos);
	void print();
	void printone(int pos);
	~myList(){//析构函数 
		dnode *p=first->next ;
		dnode *p1;
		while(p!=first){
			p1=p;
			p=p1->next ;
			delete p1;
		}
	}
	myList():first(),size(0){
		first=new dnode(0); 
		first->next =first;//当只有一个哑元节点时，该节点前后的节点就是节点本身
		first->prev =first;
	}
	int getsize(){
		return size;
	}
	
};
//输出特定节点的值 
void myList::printone(int pos){
	dnode *p=first ;
	int k=0;
	while(k!=pos){//从前到后找到那个节点 
		p=p->next ;
		k++;
	}
	cout<<p->nodeValue<<" "; 
}
// 在最后面加入节点 
void myList::push_back(int data){
	dnode *p=new dnode(data) ;
	dnode *p1=first->prev ;//p1即为最后一个节点 
	p1->next =p;//使p1 与p 连接起来 
	p->prev =p1;
    p->next =first;//是 p与first连接起来 
    first->prev =p;
	size++;	
}
//删除最后一个节点 
void myList::pop_back(){
	dnode *p=first->prev;//p为最后一个节点 
	p->prev->next =first;//使p的前一个节点与first连接 
	first->prev =p->prev ;
	size--;
	delete p;
}
//在最前面插入节点 
void myList::push_front(int data) {
	dnode *p=new dnode(data);
	p->prev =first;//使P的前一个节点为first 
	p->next =first->next ;//使P的后一个节点为原本的第一个 
	first->next->prev =p;//使first 与 p节点相连 
	first->next =p;
	size++;
	
}
//删除最前面的那个节点 
void myList::pop_front(){
	dnode *p=first->next ;//找到最前面的那个节点p 
	first->next=p->next ;//使first后的节点变为原本的第二个	
	p->next->prev=first;//使原本第二个节点与first 相连（即变为第一个节点） 
	size--;
	delete p;
	
}
//删除特定节点 
void myList::erase(int pos){
	
	int i=0;
	dnode *p=first;
	while(i!=pos){//找到特定的节点 
		p=p->next ;
		i++;
	}
	//使该节点的前一个节点 与 后一个节点相连 
    p->prev->next =p->next ;
    p->next->prev =p->prev ;
    size--;
    delete p;
    
   	
} 
//在pos 的位置 插入一个节点 
void myList::insert(int pos,int data) {
	
	int i=0;
	dnode *p1=new dnode(data);
	dnode *p=first;
	while(i!=pos){//找到pos位置的节点 
		p=p->next ;
		i++;
	}
	 
	p1->prev =p->prev ;//将要插入的节点 前面连接好 
	p->prev->next =p1;//将要插入的节点 后面连接好 
	p->prev =p1;
	p1->next =p;
	size++;
	
}
//输出每个节点的值 
void myList::print() {
	 dnode *p=first->next ;
	while(p->next!=first){//一个个往后输出 
		cout<<p->nodeValue <<" ";
		p=p->next ;
	}
	cout<<p->nodeValue <<endl;
 
}
//约瑟夫问题 找到最后出局的那个人 
void findlastone(int n,int m){
     myList l2;
     int k=0;
     while(k!=n){
     	k++;
     	l2.push_back(k);//将序号作为值加入链表中 
	 }
	 int x=1;
	 int pos=1;
	 while(l2.getsize() !=1){//当只剩一个人时不再进行 
	 	int s=l2.getsize() ;
	    pos++;//一个个报数 
	    x++;//一个个报数 
	 if(pos==s+1 )pos=1;//已经报完一轮 又要再从第一个开始 
	 if(x==m){//报到那个数了 
	 	x=0;
	 	l2.printone(pos);//将出局的序号输出 
	 	cout<<"出局"<<endl;
	 	l2.erase(pos) ;//将给节点删除 即不再参与报数 
	 	pos=pos-1;//退回前一个节点 再开始报数 
	 	
	 
	 }
}
  l2.printone(1);
  cout<<"这个人活到最后"<<endl;
}
int main(){
	/*
	//测试双向链表的各个功能 
	myList l1;
	l1.push_back(12);l1.push_back(13) ;l1.push_back(14);l1.push_back(15);
	l1.print() ;  //输出 12 13 14 15 
	l1.pop_back();l1.print() ;//输出 12 13 14 
    l1.push_front(11);l1.print() ;//输出 11 12 13 14 
    l1.pop_front();l1.print() ;//输出 12 13 14 
    l1.insert(1,11) ;l1.print() ;//输出11 12 13 14 
    l1.erase(1) ;l1.print() ;*/// 输出 12 13 14 
    
    
    int n,m;//n为总共的人数 m为报的号 
    while(cin>>n>>m)
    
    findlastone(n,m);	 
}