牛客網(wǎng)高頻算法題系列-BM2-鏈表內(nèi)指定區(qū)間反轉(zhuǎn)

題目描述

將一個(gè)節(jié)點(diǎn)數(shù)為 size 鏈表 m 位置到 n 位置之間的區(qū)間反轉(zhuǎn)，要求時(shí)間復(fù)雜度 O(n)，空間復(fù)雜度 O(1)。

原題目見：BM2 鏈表內(nèi)指定區(qū)間反轉(zhuǎn)

解法一：鏈表遍歷，指針交換

因?yàn)槠鹗嘉恢每赡苁穷^結(jié)點(diǎn)，所以首先設(shè)置一個(gè)虛擬的頭結(jié)點(diǎn)dummyNode并將next指向原有的頭結(jié)點(diǎn)，然后處理過程如下：

• 首先遍歷鏈表，找到起始位置m的前一個(gè)結(jié)點(diǎn)pre，用來記錄反轉(zhuǎn)前的結(jié)點(diǎn)；

• 然后用cur和next記錄pre的next結(jié)點(diǎn)，用next記錄cur的next結(jié)點(diǎn)；

• 然后繼續(xù)遍歷鏈表，通過交換pre、next、cur的next指針，將next結(jié)點(diǎn)轉(zhuǎn)到pre結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)處，然后循環(huán)處理cur的下一個(gè)結(jié)點(diǎn)；

• 遍歷到結(jié)束結(jié)束位置n的結(jié)點(diǎn)即反轉(zhuǎn)結(jié)束。

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

1.01^{365} ≈ 37.7834343329 ??

0.99^{365} ≈ 0.02551796445 ??

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