环形链表有m个人围成一圈，开始报数，报道n，退出，问最后剩下的是几号。

Myth丶恋晨 2022-09-24 05:22 76阅读 0赞

题目要求，10个人围成一圈，每次数到第 5 个人时些人也局，然后从下个继续开始数，依次类推最后留后的是原来顺序中的第几个人？

环形链表 有m个人围成一圈，开始报数，报道n，退出，问最后剩下的是几号。

这儿使用链表进行演示，代码如下：

环形链表.h

#include<stdio.h>
    #include<stdlib.h>
    
    struct info
    {
    	int data;
    	struct info *pNext;
    };
    
    typedef struct info node, *PNODE;
    PNODE deleteNode(PNODE phead, int data,PNODE *ptemp);	//删除数据
    int getNum(PNODE phead);	//返回链表的个数
    void showAll(PNODE phead);	//显显示全部

环形链表.c

#include"环形链表.h"
    
    
    
    void showAll(PNODE phead)	//显显示全部
    {
    	if (phead == NULL)
    	{
    		printf("链表为空！\n");
    		return;
    	}
    	else if (phead->pNext == phead)
    	{
    		printf("%d %p %p\n", phead->data, phead, phead->pNext);	//只有一个节点
    	}
    	else
    	{
    		PNODE p = phead;
    		while (p->pNext != phead)
    		{
    			printf("%d %p %p\n", p->data, p, p->pNext);	
    			p = p->pNext;
    		}
    		printf("%d %p %p\n", p->data, p, p->pNext);	//最后一个节点。
    	}
    }
    
    PNODE findFirst(PNODE phead, int data)	//检索数据
    {
    	if (phead == NULL)
    	{
    		return	NULL;
    	}
    	else if (phead->pNext == phead) //如果头节点是要查询的数据
    	{
    		return phead;
    	}
    	else
    	{
    		PNODE p = phead;
    		while (p->pNext != phead)
    		{
    			if (p->data == data)
    			{
    				return p; //如果找到返回。
    			}
    			else
    			{
    				p = p->pNext;	//找不到继续前进
    			}
    		}
    		if (p->data == data)
    			return p;
    		return NULL;
    	}
    }
    
    PNODE deleteNode(PNODE phead, int data, PNODE *ptemp)
    {
    	//先判断要删除的数据是否存在。
    	PNODE p = findFirst(phead, data);
    	if (p == NULL)
    	{
    		printf("没有检索到数据！\n");
    		return phead;
    	}
    	//删除需要使用双指针
    	PNODE p1, p2;
    	p1 = phead;
    	p2 = NULL;
    	//上面的判断要使用，否则最后一个不好判断
    	while (p1->pNext != phead)
    	{
    		if (p1->data == data)
    		{
    			break;
    		}
    		else
    		{
    			p2 = p1;
    			p1 = p1->pNext;//循环下个节点
    		}
    	}
    
    	if (p1 != phead)
    	{
    		p2->pNext = p1->pNext;
    
    		*ptemp = p1->pNext;	//指向下个节点
    		
    		free(p1);
    		p1 = NULL;
    	}
    	else
    	{
    		node *p = phead;
    		while (p->pNext != phead)
    		{
    			p = p->pNext;
    		}
    
    		phead = phead->pNext;	//改变头节点
    
    		*ptemp = p1->pNext;	//指向下个节点
    
    		free(p1);	//释放p1
    		p1 = NULL;
    		p->pNext = phead;
    
    	}
    	return phead;
    
    }
    
    
    
    int getNum(PNODE phead)	//返回链表的个数
    {
    	if (phead == NULL)
    	{
    		return 0;
    	}
    	else if (phead->pNext == phead)
    	{
    		return 1;
    	}
    	else
    	{
    		int sum = 0;
    		PNODE p = phead;
    		while (p->pNext != phead)
    		{
    			sum++;
    			p = p->pNext;
    		}
    		sum++;
    		return sum;
    	}
    }

main.c

void main()
    {
    	PNODE phead = NULL;
    	for (int i = 0; i < 10; i++)
    	{
    		phead = addBack(phead, i);
    		//phead = addFront(phead, i);
    	}
    
    	showAll(phead);
    
    	PNODE p = phead;
    	while (getNum(phead) != 1)
    	{
    		for (int i = 0; i < 4; i++)
    		{
    			p = p->pNext; 
    		}
    		//删除后需要让 p 指向下个节点，所以这儿使用了 &p.
    		phead = deleteNode(phead, p->data, &p);
    		
    		printf("\n\n");
    		showAll(phead);
    	}
    
    
    	system("pause");
    }

运行结果如下图所示：

![Center][]

[Center]: /images/20220719/8fcb5a74397d4b2fa641a4624c254fbf.png