最好的，不一定是最合適的；最合適的，才是真正最好的。💓💓💓

目錄

?說在前面

題目一：分割鏈表

題目二：環(huán)形鏈表的約瑟夫問題

SUMUP結尾

---

?說在前面

?dear朋友們大家好！💖💖💖數(shù)據(jù)結構的學習離不開刷題，繼上次算法OJ練習1，我們繼續(xù)進行鏈表經(jīng)典算法的練習。當然除了了LeetCode，有些題也會在NowCoder上，大家可以在這兩個網(wǎng)站上進行練習。

?👇👇👇

友友們！🎉🎉🎉點擊這里進入力扣leetcode學習🎉🎉🎉
?以下是leetcode題庫界面：

?

?👇👇👇

🎉🎉🎉點擊這里進入牛客網(wǎng)NowCoder刷題學習🎉🎉🎉
?以下是NowCoder題庫界面：

?

??

題目一：分割鏈表

題目鏈接：面試題 02.04. 分割鏈表 - 力扣（LeetCode）

題目描述：

?題目分析：

思路：創(chuàng)建大小鏈表，若pcur節(jié)點的值小于x則插入小鏈表，若pcur節(jié)點的值大于x則插入大鏈表，再將大小鏈表連接。

注意，實際上小鏈表的lesstail指向了原鏈表中數(shù)據(jù)為5的節(jié)點，而大鏈表的greatertail指向了原鏈表中數(shù)據(jù)為2的節(jié)點。所以在連接大小鏈表時，除了將小鏈表中的lesstail的next指針指向大鏈表中的第一個有效節(jié)點（而非頭節(jié)點）greaterhead->next，還需要將大鏈表中的greatertail的next指針置空，否則將形成循環(huán)鏈表。

代碼如下：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode* partition(struct ListNode* head, int x) {//單獨討論空鏈表的情況if(head==NULL)return NULL;  //創(chuàng)建大小指針ListNode* lesshead=(ListNode*)malloc(sizeof(ListNode));ListNode* lesstail=lesshead;ListNode* greaterhead=(ListNode*)malloc(sizeof(ListNode));ListNode* greatertail=greaterhead;ListNode* pcur=head;//遍歷數(shù)組while(pcur){if(pcur->val<x)//放入小鏈表{lesstail->next=pcur;lesstail=pcur;}else//放入大鏈表{greatertail->next=pcur;greatertail=pcur;}pcur=pcur->next;}greatertail->next=NULL;//結尾置NULLlesstail->next=greaterhead->next;連接大小鏈表ListNode* ret=lesshead->next;//保存第一個有效節(jié)點//釋放動態(tài)申請的空間free(lesshead);free(greaterhead);return ret;
}

?

題目二：環(huán)形鏈表的約瑟夫問題

題目鏈接：環(huán)形鏈表的約瑟夫問題_牛客題霸_?？途W(wǎng) (nowcoder.com)

背景：著名的約瑟夫問題

據(jù)說猶太著名歷史學家 Josephus 有過一下的故事：在羅馬人占領喬塔帕特后，39個猶太人與Joesphus 及他的朋友躲到一個洞中，39個猶太人決定寧死也不要被人抓到，于是決定了一個自殺方式，41個人排成一個圓圈，由第1個人開始報數(shù)，每報數(shù)到第3人該人就必須自殺，然后再由下一個重新報數(shù)，知道所有人都自殺身亡為止。

然而 Josephus 和他的朋友并不想遵從，Josephus 要他的朋友先假裝遵從，他將朋友與自己安排在第16個與第31個位置，于是逃過了這場死亡游戲。

題目描述：

?題目分析：

思路：利用count計數(shù)，count為m時刪除所對應的節(jié)點，直到剩下一個節(jié)點。

我們以約瑟夫事件原型為例，此時n=5，m=3，我們需要先創(chuàng)建這樣一個帶環(huán)鏈表，將它封裝為函數(shù)circle，而創(chuàng)建鏈表就需要申請節(jié)點，將其封裝為函數(shù)ListBuyNode，同時需要在帶環(huán)鏈表中把每個節(jié)點的數(shù)據(jù)設置好，這個行為我們可以用for循環(huán)完成。?

創(chuàng)建好鏈表后，我們需要創(chuàng)建兩個指針：pcur用來遍歷鏈表，每每遍歷到下一個節(jié)點count++，如果遍歷的過程中count達到m，就刪除這個節(jié)點，此時需要將pcur的前一個指針指向pcur的后一個指針，所以我們還需要指針prev來記錄pcur的前一個指針，以此往復，直到只剩下一個節(jié)點，此時pcur->next指向pcur它自己，所以循環(huán)條件就是pcur->next!=pcur。

代碼如下：

/*** 代碼中的類名、方法名、參數(shù)名已經(jīng)指定，請勿修改，直接返回方法規(guī)定的值即可** * @param n int整型 * @param m int整型 * @return int整型*/typedef struct ListNode ListNode;//創(chuàng)建節(jié)點ListNode* ListBuyNode(int x){ListNode* node=(ListNode*)malloc(sizeof(ListNode));if(node==NULL){perror("malloc");exit(1);}node->val=x;node->next=NULL;return node;}//創(chuàng)建帶環(huán)鏈表ListNode* circle(int n){ListNode* phead=ListBuyNode(1);ListNode* ptail=phead;for(int i=2;i<=n;i++){ptail->next=ListBuyNode(i);ptail=ptail->next;}ptail->next=phead;return ptail;}
int ysf(int n, int m) 
{//創(chuàng)建關于n的帶環(huán)鏈表ListNode* prev=circle(n);ListNode* pcur=prev->next;int count=1;while(pcur!=pcur->next){if(count==m){//銷毀pcur節(jié)點prev->next=pcur->next;free(pcur);pcur=prev->next;count=1;}else{prev=pcur;pcur=pcur->next;count++;}}return pcur->val;
}

?約瑟夫問題是循環(huán)鏈表的經(jīng)典應用，大家重視起來，務必熟練掌握。?

SUMUP結尾

數(shù)據(jù)結構就像數(shù)學題，需要刷題才能對它有感覺。之后還會更新數(shù)據(jù)結構相關的練習題、面試題，希望大家一起學習，共同進步~

如果大家覺得有幫助，麻煩大家點點贊，如果有錯誤的地方也歡迎大家指出~