C语言笔记34 •单链表经典算法OJ题-6.环形链表的约瑟夫问题•

环形链表的约瑟夫问题

1.问题

编号为 1 到 n 的 n 个人围成一圈。从编号为 1 的人开始报数，报到 m 的人离开。

下一个人继续从 1 开始报数。

n-1 轮结束以后，只剩下一个人，问最后留下的这个人编号是多少？

数据范围： 1≤𝑛,𝑚≤100001≤n,m≤10000

进阶：空间复杂度 𝑂(1)O(1)，时间复杂度 𝑂(𝑛)O(n)

2.代码实现

//6.环形链表的约瑟夫问题
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>typedef int SLTDataType;typedef struct SListnode
{SLTDataType val;struct SListnode* next;
}ListNode;ListNode* createNode(SLTDataType val)
{ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));if (newnode == NULL){perror("malloc");exit(1);}newnode->val = val;newnode->next = NULL;return newnode;
}//创建带环链表
ListNode* createCircleList(int n)
{ListNode* phead= createNode(1);ListNode* ptail = phead;for (int i = 2; i <= n; i++){ptail->next = createNode(i);ptail = ptail->next;}ptail->next = phead;//首尾相连，链表成环return ptail;
}int person_num(int n,int m)
{ListNode* ptail = createCircleList(n);ListNode* pcur = ptail->next;int count = 1;while (ptail->next != ptail){if (count == m)//销毁节点{ptail->next = pcur->next;free(pcur);pcur = ptail->next;count = 1;}else{ptail = ptail->next;//等价于ptail = pcur;pcur  = pcur->next;count++;}}return ptail->val;}int main()
{int person = person_num(5, 2);printf("%d", person);return 0;
}