鏈接:環形鏈表的約瑟夫問題_牛客題霸_牛客網【點擊即可跳轉】
著名的Josephus問題據說著名猶太歷史學家 Josephus有過以下的故事:? 在羅馬人占領喬塔帕特后,39 個猶太?與 Josephus及他的朋友躲到?個洞中,39個猶太?決定寧愿死也不要被?抓到,于是決定了?個自殺方式,41個?排成?個圓圈,由第1個?開始報數,每報數到第3人,該人就必須自殺,然后再由下一個重新報數,直到所有?都自殺身亡為止。然而Josephus 和他的朋友并不想遵從,Josephus要他的朋友先假裝遵從,他將朋友與自己安排在 第16個與第31個位置,于是逃過了這場死亡游戲。
思路:
1.創建帶環鏈表
2.count計數(報到m,就刪掉)
代碼實現:
/*** 代碼中的類名、方法名、參數名已經指定,請勿修改,直接返回方法規定的值即可** * @param n int整型 * @param m int整型 * @return int整型*/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* createNode(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 )
{ListNode*prev=createNode(n);ListNode*pcur=prev->next;int count=1;while(pcur->next!=pcur)//只有一個節點,就跳出循環{if(count==m) {prev->next=pcur->next;free(pcur); //銷毀pcur節點pcur=prev->next;count=1;}else {prev=pcur;pcur=pcur->next;count++;}}return pcur->val;//此時剩下的一個節點 就是要返回的節點里的值
}
感謝觀看,如果對你有所幫助的話,點贊支持一下吧^.^