?？途W(wǎng)高頻算法題系列-BM12-單鏈表的排序

題目描述

描述

原題目見：BM12 單鏈表的排序

解法一：數(shù)組排序

首先判斷如果鏈表為空或者只有一個結(jié)點(diǎn)，則不需要排序，直接返回原鏈表。

否則，使用額外空間進(jìn)行排序，處理過程如下：

• 首先遍歷鏈表，將所有結(jié)點(diǎn)值暫存在一個List中；

• 然后，使用庫函數(shù)將List排序（也可以使用各種排序算法進(jìn)行排序）；

• 最后，將排序后的結(jié)點(diǎn)值構(gòu)造成新的鏈表并返回。

解法二：歸并排序

使用遞歸的方式，將原鏈表排序，遞歸處理過程如下：

• 首先也是要判斷如果鏈表為空或者只有一個結(jié)點(diǎn)，則不需要處理，直接返回原鏈表；

• 然后，使用快慢指針尋找鏈表的中點(diǎn)位置；

• 然后，遞歸調(diào)用分別排序中點(diǎn)左右的兩個鏈表；

• 然后，將左右鏈表合并；

• 最后，返回合并后的鏈表。

代碼

1.01^{365} ≈ 37.7834343329 ??

0.99^{365} ≈ 0.02551796445 ??

相信堅持的力量！