?？途W(wǎng)高頻算法題系列-BM14-鏈表的奇偶重排

題目描述

給定一個單鏈表，請設(shè)定一個函數(shù)，將鏈表的奇數(shù)位節(jié)點和偶數(shù)位節(jié)點分別放在一起，重排后輸出。 注意是節(jié)點的編號而非節(jié)點的數(shù)值。

原題目見：BM14 鏈表的奇偶重排

解法一：鏈表遍歷（使用額外空間）

首先，判斷如果鏈表為空或者只有1或2個結(jié)點，不用重排，直接返回原鏈表。

否則，使用2個list額外記錄奇數(shù)和偶數(shù)位的結(jié)點，處理過程如下：

• 遍歷鏈表，分別將奇數(shù)和偶數(shù)位的結(jié)點值放到不同的list中；

• 按照奇數(shù)位在前、偶數(shù)位在后的順序，將2個list中的值重組成新的鏈表即為重排后的鏈表，返回之。

解法二：雙指針法

同樣的，首先要判斷如果鏈表為空或者只有1或2個結(jié)點，不用重排，直接返回原鏈表。

否則，使用odd和even結(jié)點分別指向鏈表的第一個（奇數(shù)）和第二個（偶數(shù)）結(jié)點，然后遍歷鏈表，將奇數(shù)位的結(jié)點和偶數(shù)位的結(jié)點分別連接起來，最后，將偶數(shù)位的放到奇數(shù)位的鏈表后面，即為重排后的鏈表。

代碼

1.01^{365} ≈ 37.7834343329 ??

0.99^{365} ≈ 0.02551796445 ??

相信堅持的力量！