?？途W(wǎng)高頻算法題系列-BM1 反轉(zhuǎn)鏈表

題目描述

給定一個(gè)單鏈表的頭結(jié)點(diǎn)pHead(該頭節(jié)點(diǎn)是有值的)，長度為n，反轉(zhuǎn)該鏈表后，返回新鏈表的表頭。

原題目見：BM1 反轉(zhuǎn)鏈表

解法一：結(jié)點(diǎn)反轉(zhuǎn)

• 首先，如果head為空或者只有一個(gè)結(jié)點(diǎn)，直接返回。

• 否則，分別用first和next指針指向鏈表的前兩個(gè)結(jié)點(diǎn)，并將它們的next指針域反轉(zhuǎn)，然后繼續(xù)往后遍歷處理鏈表的后續(xù)結(jié)點(diǎn)直到將最后一個(gè)結(jié)點(diǎn)反轉(zhuǎn)。注意，需要將head頭結(jié)點(diǎn)的next指向null。

• 最后，返回first結(jié)點(diǎn)，即為反轉(zhuǎn)后的新鏈表的頭結(jié)點(diǎn)。

解法二：遞歸法

• 同樣的，首先需要判斷，如果head為空或者只有一個(gè)結(jié)點(diǎn)，直接返回。

• 否則，通過遞歸的方式來處理，遞歸的處理流程如下：

• 遞歸的終結(jié)條件是head結(jié)點(diǎn)為空或者沒有下一個(gè)結(jié)點(diǎn)；

• 否則，遞歸得到head.next的反轉(zhuǎn)鏈表為reverse，然后將reverse的next指針指向head，同樣要記住需要將head頭結(jié)點(diǎn)的next指向null。

1.01^{365} ≈ 37.7834343329 ? 0.99^{365} ≈ 0.02551796445 ? 相信堅(jiān)持的力量！