经典算法面试题:环形链表的约瑟夫问题
目录:
1.题目描述
2.示例1
3.示例2
—————————————————————————————————————————————————————
正文开始
著名的Josephus问题
据说著名犹太历史学家 Josephus有过以下的故事:在罗马人占领乔塔帕特后,39 个犹太人与]osephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被人抓到,于是决定了一个自杀方式,41个人排成一个圆圈,由第1个人开始报数,每报数到第3人该人就必须自杀,然后再由下一个重新报数,直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想道从,Josephus要他的朋友先假装遵从,他将朋友与自己安排在第16个与第31个位置,于是逃过了这场死亡游戏。
1.题目描述
2.示例1
3.示例2
/** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param n int整型 * @param m int整型 * @return int整型 */ #include <stdlib.h> typedef struct ListNode ListNode; //创建节点 ListNode* buyNode(int x) { ListNode* node = (ListNode*)malloc(sizeof(ListNode)); if(node == NULL) { exit(1); } node->val = x; node->next = NULL; return node; } //创建带环链表 ListNode* createCircle(int n) { //先创建第一个节点 ListNode* phead = buyNode(1); ListNode* ptail = phead; for (int i = 2; i <= n; i++) { ptail->next = buyNode(i); ptail = ptail->next; } //首尾相连,链表成环 ptail->next = phead; return ptail; } int ysf(int n, int m ) { //1.根据n创建带环链表 ListNode* prev = createCircle(n); ListNode* pcur = prev->next; int count = 1; //当链表中只有一个节点的情况 while(pcur->next != pcur) { if(count == m) { //销毁pcur节点 prev->next = pcur->next; free(pcur); pcur = prev->next; count = 1; }else{ //此时不需要销毁节点 prev = pcur; pcur = pcur->next; count++; } } //此时剩下的一个节点就是返回的节点的“值” int ret = pcur->val; free(pcur); pcur = NULL; return ret; }
最后养成一个好习惯,在代码的第61行到64行,return之前也可以先把pcur节点释放掉(不要忘了提前把val存下来~)。