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

目錄

?說(shuō)在前面

題目一：分割鏈表

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

SUMUP結(jié)尾

---

?說(shuō)在前面

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

?👇👇👇

友友們！🎉🎉🎉點(diǎn)擊這里進(jìn)入力扣leetcode學(xué)習(xí)🎉🎉🎉
?以下是leetcode題庫(kù)界面：

?

?👇👇👇

🎉🎉🎉點(diǎn)擊這里進(jìn)入牛客網(wǎng)NowCoder刷題學(xué)習(xí)🎉🎉🎉
?以下是NowCoder題庫(kù)界面：

?

??

題目一：分割鏈表

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

題目描述：

?題目分析：

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

注意，實(shí)際上小鏈表的lesstail指向了原鏈表中數(shù)據(jù)為5的節(jié)點(diǎn)，而大鏈表的greatertail指向了原鏈表中數(shù)據(jù)為2的節(jié)點(diǎn)。所以在連接大小鏈表時(shí)，除了將小鏈表中的lesstail的next指針指向大鏈表中的第一個(gè)有效節(jié)點(diǎn)（而非頭節(jié)點(diǎn)）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) {//單獨(dú)討論空鏈表的情況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;//結(jié)尾置NULLlesstail->next=greaterhead->next;連接大小鏈表ListNode* ret=lesshead->next;//保存第一個(gè)有效節(jié)點(diǎn)//釋放動(dòng)態(tài)申請(qǐng)的空間free(lesshead);free(greaterhead);return ret;
}

?

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

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

背景：著名的約瑟夫問(wèn)題

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

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

題目描述：

?題目分析：

思路：利用count計(jì)數(shù)，count為m時(shí)刪除所對(duì)應(yīng)的節(jié)點(diǎn)，直到剩下一個(gè)節(jié)點(diǎn)。

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

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

代碼如下：

/*** 代碼中的類名、方法名、參數(shù)名已經(jīng)指定，請(qǐng)勿修改，直接返回方法規(guī)定的值即可** * @param n int整型 * @param m int整型 * @return int整型*/typedef struct ListNode ListNode;//創(chuàng)建節(jié)點(diǎn)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)建關(guān)于n的帶環(huán)鏈表ListNode* prev=circle(n);ListNode* pcur=prev->next;int count=1;while(pcur!=pcur->next){if(count==m){//銷毀pcur節(jié)點(diǎn)prev->next=pcur->next;free(pcur);pcur=prev->next;count=1;}else{prev=pcur;pcur=pcur->next;count++;}}return pcur->val;
}

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

SUMUP結(jié)尾

數(shù)據(jù)結(jié)構(gòu)就像數(shù)學(xué)題，需要刷題才能對(duì)它有感覺(jué)。之后還會(huì)更新數(shù)據(jù)結(jié)構(gòu)相關(guān)的練習(xí)題、面試題，希望大家一起學(xué)習(xí)，共同進(jìn)步~

如果大家覺(jué)得有幫助，麻煩大家點(diǎn)點(diǎn)贊，如果有錯(cuò)誤的地方也歡迎大家指出~