目錄
前言?
一.故事背景
二.題目?
?編輯三.思路
1）數組
?編輯2） 循環鏈表
四.代碼實現?
搭配食用更佳哦~~
數據結構之單單單——鏈表-CSDN博客
數據結構之單鏈表的基本操作-CSDN博客
前面學了單鏈表的相關知識，我們來嘗試做一下關于順序表的經典算法題~?
前言?
? ? ? 這次是牛客上的一道題，是循環鏈表的經典應用，講的是一個老六用自己的聰明才智躲過被殺的命運。
環形鏈表的約瑟夫問題_牛客題霸_牛客網 (nowcoder.com)
https://www.nowcoder.com/practice/41c399fdb6004b31a6cbb047c641ed8a?tpId=196&tqId=37145&ru=/exam/oj
一.故事背景
? ? ? ? Josephus 問題是一個古老而著名的問題，最早的記載來自猶太歷史學家弗拉維奧·約瑟夫斯（FlaviusJosephus），他在猶太戰爭中被羅馬軍隊包圍，為了不被俘虜，他和他的 39 個戰友決定自殺，但是他們并不想自己親手殺死自己，于是決定站在一個圓圈里，從一個人開始，每報數到第 14 個人，第 14 個人就會被殺掉，然后從下一個人開始重新報數，直到最后只剩下一個人，那個人就可以幸存。
二.題目?
三.思路
1）數組
?用數組的話我們需要先申請空間，然后再計數，每記到2就嘎掉它，可以給他賦值一個數組不存在的數比如 0 ，當報數到最后一個時我們需要返回數組最開始也就是下標為 0的時候，當剩下最后一個時就得到了活著的那一個，因為數組比較麻煩而且本篇要講的是環形鏈表，所以這個代碼就不寫了，僅敘述一下思路
2） 循環鏈表
? ? ?顧名思義，循環鏈表就是把原本線性的鏈表成環，如何實現呢？我們都知道鏈表尾節點指針指向NULL，所以我們把這個指針指向頭節點就可以搞出一個循環鏈表。
? 和上一個思路一樣，我們依舊讓他們循環報數，報到 2 的嘎掉，在刪除這個節點的同時我們需要將前一個節點的 next 指針指向被嘎節點的下一個指針，這樣才能使鏈表連續起來
雖然畫的蠻亂的，大致意思一樣，最終結果就是第三個節點自己指向自己。
總結思路就兩步：
- 創建帶環鏈表
- 計數，嘎節點
四.代碼實現?
/*** 代碼中的類名、方法名、參數名已經指定，請勿修改，直接返回方法規定的值即可** * @param n int整型 * @param m int整型 * @return int整型*/
#include <stdlib.h>
typedef struct ListNode ListNode;
//創建節點
ListNode* buyNoded(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 = buyNoded(1);ListNode* ptail = phead;for (int i = 2; i<= n; i++) {ptail->next = buyNoded(i);ptail = ptail->next;}ptail->next = phead;return ptail;
}
int ysf(int n, int m ) {// write code here//創建帶環鏈表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++;}}//剩下的就是要返回的值了return pcur->val;
}這道題到這就結束啦~雖然循環鏈表寫起來比較麻煩要封裝好多函數，但封裝完就好寫啦~~
? ? 🎈🎈完結撒花🎈🎈??
