问题

【Q】一群猴子，编号是1，2，3 …m，这群猴子（m个）按照1~m的顺序围坐一圈。从第1只开始数，每数到第n个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。输入m和n，输出为大王的猴子是几号。

代码

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

/* 定义链表节点类型 */
typedef struct node
{
	int data;
	struct node* next;
} linkList;


int main(void)
{
	int i = 0;
	int allNum = 10, outNum = 4, kingNum;

	/*printf("猴子数量 = ");
	scanf("%d",&allNum);

	printf("输入数到第n只猴子出局，n=");
	scanf("%d", &outNum);*/

	linkList* pCurrent;
	linkList* pNew;

	/* 链表头节点初始化 */
	linkList* pHead;

	pHead = (linkList*)malloc(sizeof(linkList));
	pCurrent = pHead;
	pCurrent->data = 1;
	pCurrent->next = pCurrent;	// 指向自己

	/* 初始化循环链表 */
	for (i = 2; i <= allNum; i++)
	{
		pNew = (linkList*)malloc(sizeof(linkList));
		pNew->data = i;
		pNew->next = pCurrent->next;	// pCurrent为当前链表中的最后一个节点，其*next指向头节点地址
		pCurrent->next = pNew;
		pCurrent = pCurrent->next;		// 将链表最后一个节点指向新节点
	}

	pCurrent = pHead;	// 回到第一只猴子

	int total = allNum;	// 记录当前剩余的猴子
	linkList* pBefore;
	linkList* pDelete;

	pBefore = pHead;

	// 默认从第一只猴子开始数
	while (total != 1)
	{
		// 指向要删除的猴子
		for (i = 1; i < outNum; i++)
		{
			pCurrent = pCurrent->next;	
		}

		printf("要删除的猴子是：[%d] 号\n", pCurrent->data);

		// 找到要删除的猴子前面的那只猴子（前驱）
		while (pBefore->next != pCurrent)
		{
			pBefore = pBefore->next;
		}

		// 将删除猴子后的链表连接起来
		pBefore->next = pCurrent->next;

		// 保存要删除的猴子
		pDelete = pCurrent;

		// 指向要删除的猴子后面的那只猴子（后继）
		pCurrent = pCurrent->next;

		// 删除节点
		free(pDelete);

		total--;
	}

	printf("\n\n猴王是:[%d] 号\n\n", pCurrent->data);

	free(pCurrent);

	return 0;
}