约瑟夫环超详细简单思路！（循环链表）

约瑟夫环超详细简单思路！（循环链表）"/>

约瑟夫环超详细简单思路！（循环链表）

约瑟夫环 (100分)
N个人围成一圈顺序编号，从1号开始按1、2、3…顺序报数，报p者退出圈外，其余的人再从1、2、3开始报数，报p的人再退出圈外，以此类推。 请按退出顺序输出每个退出人的原序号。

输入格式:
输入只有一行，包括一个整数N(1<=N<=3000)及一个整数p(1<=p<=5000)。

输出格式:
按退出顺序输出每个退出人的原序号，数据间以一个空格分隔，但行尾无空格。

输入样例:
在这里给出一组输入。例如：

7 3

输出样例:
3 6 2 7 5 1 4

目前在学循环链表，所以用的循环链表写。
这是我目前想到的最简单的解决方法，比较直接（我还没有想到其他方法哈哈哈）
按照测试用例 选择 7 3来看，容易知道输出顺序是这样的：

我的想法是访问一个节点后，就把节点的值赋值为0，然后后面用if语句判断是否为0，决定是否输出，不为0就输出数据，为0就跳过。


用的尾插法
步骤：

1. 创建链表节点
2. 创建循环链表
3. 关键代码解决约瑟夫问题
   
   
   
   

WA代码：

#include <stdio.h>
#include <stdlib.h>/* run this program using the console pauser or add your own getch, system("pause") or input loop */
typedef struct node
{int data;struct node *next;
}node;
int main(int argc, char *argv[]) 
{node *head = NULL;head = (node*)malloc(sizeof(node));head->data = 1;head->next = NULL;node *p = head;//尾插法建造链表 int i,n,k;scanf("%d",&n);scanf("%d",&k);//针对约瑟夫问题可以使用for循环来建立链表 for(i=2;i<=n;i++){node *q = NULL;q = (node*)malloc(sizeof(node));q->data = i;q->next = NULL;p->next = q; p = q;q = q->next;}p->next = head;/*p = head是行不通的必须得令一个新指针t指向p debug:验证循环链表 node *t = p;t = head;while(t!=NULL){printf("%d ",t->data);t = t->next;}*///以上代码把数据为1~n的循环链表建立成功 //约瑟夫问题：int cnt = 1;node *t = p;t = head;while(t!=NULL){if(cnt!=k){if(t->data!=0){cnt++;}t = t->next;}else{//第一次遍历时遇到满足条件的元素就输出，然后赋值为0 if(t->data!=0){cnt = 1;printf("%d ",t->data);t->data = 0;}t = t->next;}}t = head;while(t!=NULL){t = t->next;free(head);head = t;}return 0;	
}

循环条件里用的 t ！= NULL是错误的，（就算销毁完了链表，还是无法跳出循环？？）；

AC题解：

#include <stdio.h>
#include <stdlib.h>/* run this program using the console pauser or add your own getch, system("pause") or input loop */
typedef struct node
{int data;struct node *next;
}node;
int main(int argc, char *argv[])
{node *head = NULL;head = (node*)malloc(sizeof(node));head->data = 1;head->next = NULL;node *p = head;//尾插法建造链表int i,n,k;scanf("%d",&n);scanf("%d",&k);//针对约瑟夫问题可以使用for循环来建立链表for(i=2;i<=n;i++){node *q = NULL;q = (node*)malloc(sizeof(node));q->data = i;q->next = NULL;p->next = q;p = q;q = q->next;}p->next = head;node* q = head;/*p = head是行不通的必须得令一个新指针t指向pdebug:验证循环链表node *t = p;t = head;while(t!=NULL){printf("%d ",t->data);t = t->next;}*///以上代码把数据为1~n的循环链表建立成功//约瑟夫问题：int cnt = 1;node *t = p;t = head;int x = 0;//这里引入x的意义是在于方便对比循环次数while(x != n){if(cnt!=k){if(t->data!=0){cnt++;}t = t->next;}else{//第一次遍历时遇到满足条件的元素就输出，然后赋值为0if(t->data!=0){cnt = 1;x++;printf("%d",t->data);if(x != n)printf(" ");t->data = 0;}t = t->next;}}t = head;x = 0;//注意循环条件不能是while(t!=NULL)while(x != n){t = t->next;free(head);x++;head = t;}return 0;
}

可以用x计数，x作为判断循环是否进入的条件

继续努力。