圆圈中最后剩下的数字

 题目：0,1，....，n-1这n个数字排成一个圆圈，从数字0开始每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。

解法一  循环链表

 用循环链表模拟圆圈，一次删除第m个数字。这里并未采用末班库中的函数而是自行建立循环链表（只设计用到的功能函数）。

循环链表部分

struct ListNode
{
	int value;
	ListNode* next;
};
//链表节点的创建
ListNode* createNode(int value)
{
	ListNode* node = new ListNode();
	node->value = value;
	node->next = NULL;
	return node;
}
//循环链表的大小
int Listsize(ListNode* head)
{
   if(head==NULL)return -1;
	ListNode* node = head;
	int i = 0;
	while (node->next != head)
	{
		i++;
		node = node->next;
	}
	i++;
	return i;
}
//循环链表的创建
ListNode* createCircleList(int n)
{

        if（n<=0）return NULL;
	ListNode* head = createNode(0);
	ListNode* node = head;
	for (int i = 1; i < n;i++)
	{
		node->next = createNode(i);
		node = node->next;
	}
	node->next = head;
	return head;
}
删除圆圈中第m个数的函数
void deletenode(ListNode* head,int m)
{
	if (head==NULL||m<1)return;
	ListNode* node = head;
	while (Listsize(node)>1)
	{
		int i = 1;
		while (i < m-1)
		{
			node = node->next;
			i++;
		}
		ListNode* deletenode = node->next;
		ListNode* nextnode = node->next->next;
		node->next = nextnode;
		delete deletenode;
		node = nextnode;
	}
//输出最后一个数字
	cout << node->value;
}
int main()
{
//创建0,1,2,3,4,5的循环链表
	ListNode* head = createCircleList(6);
 //依次删除第4个数字	
deletenode(head,4);
	return 0;
}