牛客網(wǎng)高頻算法題系列-BM9-刪除鏈表的倒數(shù)第n個(gè)節(jié)點(diǎn)

題目描述

給定一個(gè)鏈表，刪除鏈表的倒數(shù)第 n 個(gè)節(jié)點(diǎn)并返回鏈表的頭指針

原題目見(jiàn)：BM9 刪除鏈表的倒數(shù)第n個(gè)節(jié)點(diǎn)

解法一：雙指針?lè)?/h1>

首先，考慮兩種特殊情況：

• 如果原鏈表為空，直接返回null。

• 如果k不是正數(shù)，直接返回null。

否則，使用雙指針求解，求解過(guò)程如下：

• 因?yàn)橛锌赡軇h掉頭結(jié)點(diǎn)，所以先設(shè)置一個(gè)假的頭結(jié)點(diǎn)dummyNode，并指向原有的頭結(jié)點(diǎn)；

• 然后，遍歷鏈表，將fast結(jié)點(diǎn)指向第n-1個(gè)結(jié)點(diǎn)；

• 如果遍歷完后fast為null或者fast的next為空，說(shuō)明鏈表長(zhǎng)度小于n，不存在倒數(shù)第n個(gè)結(jié)點(diǎn)，直接返回null；

• 否則，快慢指針一起移動(dòng)，直到fast移動(dòng)到倒數(shù)第二個(gè)結(jié)點(diǎn)，此時(shí)，slow即為倒數(shù)第n+1個(gè)結(jié)點(diǎn)；

• 然后將slow的next結(jié)點(diǎn)即倒數(shù)第n個(gè)結(jié)點(diǎn)移除；

• 最后返回dummyNode.next即為刪除第n個(gè)結(jié)點(diǎn)后的新鏈表。

代碼

1.01^{365} ≈ 37.7834343329 ??

0.99^{365} ≈ 0.02551796445 ??

相信堅(jiān)持的力量！