第1關(guān)：查找倒數(shù)第k個(gè)數(shù)

思路分析

遍歷一遍統(tǒng)計(jì)一共有多少個(gè)節(jié)點(diǎn)，由于p=L->next,從第一個(gè)節(jié)點(diǎn)開(kāi)始尋找，所以計(jì)算器cnt初始化為1，如果還有后續(xù)節(jié)點(diǎn)，我們就繼續(xù)查找，然后L重新回到L->next（第一個(gè)節(jié)點(diǎn)），然后進(jìn)行查找，當(dāng)節(jié)點(diǎn)數(shù)達(dá)到 i ==cnt-k+1則說(shuō)明找到了，返回p即可。

代碼展示

第2關(guān)：鏈表逆置

思路分析

原理非常簡(jiǎn)單，即把下一個(gè)節(jié)點(diǎn)的next指向當(dāng)前節(jié)點(diǎn)，即p->next=pre,其中pre保存前一節(jié)點(diǎn)，p是當(dāng)前節(jié)點(diǎn)。

代碼展示

第3關(guān)：有序單鏈表的就地合并

代碼展示

第4關(guān)：兩個(gè)一元多項(xiàng)式異地相加

代碼展示

第5關(guān)：約瑟夫環(huán)問(wèn)題

代碼展示

今日總結(jié)

• 1鏈表遍歷是非常非常參見(jiàn)的，必須掌握。

• 2鏈表的長(zhǎng)度未知時(shí)，我們可以先遍歷鏈表，同時(shí)計(jì)數(shù)，就可以知道鏈表的長(zhǎng)度了，在刪除倒數(shù)第k個(gè)數(shù)中非常能夠體現(xiàn)。

• 3鏈表反轉(zhuǎn)的時(shí)候只需要記憶當(dāng)前節(jié)點(diǎn)和前一個(gè)節(jié)點(diǎn)，進(jìn)行反抓即可，需要注意的是pre初始化應(yīng)該是NULL，因?yàn)榉崔D(zhuǎn)后是鏈表末尾。最后鏈表L->next=pre是把鏈表頭指向pre。

• 4多項(xiàng)式的合并這一題主要是和順序表差不多，注意這一題要求答案存儲(chǔ)在C中，并且A，B不改變，所以每次插入一個(gè)節(jié)點(diǎn)到C中都不能直接使用A，B中的節(jié)點(diǎn)，需要我們new一個(gè)新的節(jié)點(diǎn)，保持A，B鏈表的原樣。

• 約瑟夫環(huán)是一個(gè)經(jīng)典問(wèn)題，網(wǎng)絡(luò)上也有很多解答，這里就不重點(diǎn)介紹了，需要掌握循環(huán)鏈表的創(chuàng)建和單鏈表的遍歷即可。