【100题】第十八题（约瑟夫循环）

一，题目：n个数字（0,1,…,n-1）形成一个圆圈，从数字0开始，每次从这个圆圈中删除第m个数字（第一个为当前数字本身，第二个为当前数字的下一个数字）。当一个数字删除后，从被删除数字的下一个继续删除第m个数字。求出在这个圆圈中剩下的最后一个数字。

二，思路：创建一个循环链表，每次走m步删除一个节点，最后剩下一个

三，源码：

#include <iostream>
#include "malloc.h"
using namespace std;
struct node
{
   int data;
   node *next;	
};

node *createList(int a[],int n)
{
	node *head;
	node *p,*q;
	head=(node *)malloc(sizeof(node));
	head->data=0;
	head->next=NULL;
	for(int i=0;i<n;i++)
	{
		p=(node *)malloc(sizeof(node));
		p->data=a[i];
		p->next=NULL;
		
		p->next=head->next;
		head->next=p;
		
	}
	q=head;
	while(q->next!=NULL)
	    q=q->next;
 
     q->next=head;
	
		
	return head;
}
void display(node *head)
{
	node *p;
	p=head;
    cout<<p->data<<endl;
	while(p->next!=head)
    {	   
	   p=p->next;
	   cout<<p->data<<endl;
    }
}
void deleteNode(node *head,int m)
{
	node *p,*q;
	p=head;
	
	while(p->next!=head)//p为head前一个节点 
	   p=p->next;
	   
	while(p->next!=p)
	{
		q=p->next;
		for(int i=1;i<m;i++)//走几步 
		{
			p=q;
			q=q->next;	
		}
		p->next=q->next;//删除节点 
		cout<<"delete node is:"<<q->data<<endl; 
	}
	
	cout<<"last node is:"<<p->data<<endl; 
}
int main()
{
	
	int a[10]={1,2,3,4,5,6,7,8,9};
	node *head;
	head=createList(a,9);
	display(head);
	//cout<<head->data;
	deleteNode(head,2);
	return 0;
}