链表——约瑟夫问题 百练2746

约瑟夫问题

建立循环链表，一次删除符合结点，最后剩下一个即为所求结点

#include <iostream>
#include <stdio.h>
#include <stdlib.h>

using namespace std;

struct node 
{
	int num;
	node * next;
};

void initqueen(int n,node * queen)
{
	int i;
	node * r,*s;
	r=s=queen;

	for(i=2;i<=n;i++)//2到n结点
	{
		
		s = (node *)malloc(sizeof(node));
		s->num = i;
		s->next = NULL;
		r->next = s;
		r = s;
	}
//	printf("r=%d\n",r->num);
	r->next = queen;//最后一个结点指向头结点，形成循环队列
}
int solve(int n,int m,node * queen)
{
	int i,j;
	node * s;
	node *p = queen;
//	printf("q = %d\n",queen->num);

	s = p;
	for(i=1;i<n;i++)
	{
		
	//	printf("p=%d\n",p->num);
		for(j=1;j<m;j++)
		{
			
			s = p;
			p=p->next;
		//	s = p;
		}
	//	printf("*p=%d\n",p->num);
		s->next = p->next;
		free(p);
		p = s->next;
	}
	return p->num;
}
int main()
{
 	int m,n;
	node * queen;
 	while(scanf("%d%d",&n,&m),m&&n)
 	{ 
	//	printf("n=%d,m=%d\n",n,m);
		
	 	if(n==1) {
			printf("1\n");	continue;
	 	}
		if(m==1){
			printf("%d\n",n); continue;
		}
		queen = (node *)malloc(sizeof(node)); //第一个结点
		queen->num = 1;
		queen->next = NULL;;
		 initqueen(n,queen);
		 printf("%d\n",solve(n,m,queen));					   								
	}
 	return 0;
}