下列C++代码用循环链表解决约瑟夫问题,即假设 n 个人围成一圈,从第一个人开始数,每次数到第 k 个的人就出圈,输出最后留下的那个人的编号。横线上应填写( )。
struct Node{
int data;
Node* next;
};
Node* createcircularList(int n){
Node* head= new Node{1, nullptr};
Node* prev= head;
for(inti=2;i<= n; ++i){
Node* node = new Node{i, nullptr};
prev->next= node:
prev = node;
}
prev->next=head;
return head;
}
int fingLastsurvival(int n,int k){
Node* head = createcircularList(n);
Node*p= head;
Node* prev= nullptr;
while(p->next != p){
for(int count=1;count<k;++count){
prev =p;
p= p->next;
}
__________________
}
cout<<"最后留下的人编号是:"<<p->data<< endl;
delete p;
return 0;
}
prev->next=p->next;
delete p;
p = prev->next;
delete p;
prev->next=p->next;
p= prev->next;
delete p;
p = prev->next;
prev->next=p->next;
prev->next=p->next;
p = prev->next;
delete p;