?？途W(wǎng)高頻算法題系列-BM8-鏈表中倒數(shù)最后k個(gè)結(jié)點(diǎn)

題目描述

描述：輸入一個(gè)長(zhǎng)度為 n 的鏈表，設(shè)鏈表中的元素的值為 ai ，返回該鏈表中倒數(shù)第k個(gè)節(jié)點(diǎn)。如果該鏈表長(zhǎng)度小于k，請(qǐng)返回一個(gè)長(zhǎng)度為 0 的鏈表。

原題目見(jiàn)：BM8 鏈表中倒數(shù)最后k個(gè)結(jié)點(diǎn)

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

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

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

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

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

• 首先，遍歷鏈表，將fast結(jié)點(diǎn)指向第k個(gè)結(jié)點(diǎn)；

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

• 否則，快慢指針一起移動(dòng)，直到fast移動(dòng)到最后一個(gè)結(jié)點(diǎn)，此時(shí)，slow即為倒數(shù)第k個(gè)結(jié)點(diǎn)，返回之。

代碼

1.01^{365} ≈ 37.7834343329 ??

0.99^{365} ≈ 0.02551796445 ??

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