题目描述
n个人围成一个圈，每个人分别标注为1、2、...、n，要求从1号从1开始报数，报到k的人出圈，接着下一个人又从1开始报数，如此循环，直到只剩最后 一个人时，该人即为胜利者。例如当n=10,k=4时，依次出列的人分别为4、8、2、7、3、10，9、1、6、5，则5号位置的人为胜利者。给定n个 人，请你编程计算出最后胜利者标号数。（要求用单循环链表完成。）
input
第一行为人数n;
第二行为报数k
output
输出最后胜利者的标号数。
样例输入
10
4
样例输出
5
这道题的思路是构建一个环形链表，然后用一个指针在环形链表上移动，找出最后的胜利者。
代码如下
1 #include<iostream> 2 #include<stdlib.h> 3 using std::cin; 4 using std::cout; 5 using std::endl; 6 7 int n; 8 struct node{ 9 int num; 10 node*next; 11 }; 12 13 node*create(node*head){ 14 int a=1; 15 head=(node*)malloc(sizeof(node)); 16 node*p=NULL,*q=NULL; 17 p=head; 18 p->num=1; 19 p->next=head; 20 int i; 21 for(i=1;i<n;i++){ 22 q=(node*)malloc(sizeof(node)); 23 p->next=q; 24 q->num=i+1; 25 q->next=head; 26 p=q; 27 } 28 return head; 29 } 30 node*del(node*p,int m){ 31 int i; 32 for(i=2;i<m;i++){ 33 p=p->next; 34 } 35 node*temp=NULL; 36 temp=p->next; 37 p->next=temp->next; 38 free(temp); 39 return p; 40 } 41 int main(){ 42 node*p=NULL; 43 cin>>n; 44 p=create(p); 45 int m; 46 cin>>m; 47 int t=n; 48 for(int i=1;i<n;i++){ 49 p=del(p,m); 50 p=p->next; 51 } 52 cout<<p->num; 53 return 0; 54 }