給你鏈表的頭結(jié)點(diǎn)?head?，請(qǐng)將其按?升序?排列并返回?排序后的鏈表?。

?

示例 1：

輸入：head = [4,2,1,3]輸出：[1,2,3,4]

示例 2：

輸入：head = [-1,5,3,4,0]輸出：[-1,0,3,4,5]

示例 3：

輸入：head = []輸出：[]

其主要思路是使用歸并排序的方法，將鏈表分成左右兩個(gè)部分，對(duì)每個(gè)部分進(jìn)行排序后再進(jìn)行合并。

具體來(lái)說(shuō)，sortList函數(shù)就是對(duì)整個(gè)鏈表進(jìn)行排序的函數(shù)，它調(diào)用了mergeSort函數(shù)對(duì)鏈表進(jìn)行歸并排序。如果鏈表為空或者只有一個(gè)節(jié)點(diǎn)，那么就可以直接返回鏈表本身。

mergeSort函數(shù)使用快慢指針的方法找到鏈表的中間節(jié)點(diǎn)，然后將鏈表分成左右兩個(gè)部分，對(duì)每個(gè)部分分別調(diào)用mergeSort函數(shù)進(jìn)行排序，然后再調(diào)用mergeList函數(shù)進(jìn)行合并。注意，在分割鏈表時(shí)，要將中間節(jié)點(diǎn)的next指針設(shè)置為nullptr，否則會(huì)出現(xiàn)環(huán)形鏈表。

mergeList函數(shù)就是將左右兩個(gè)已經(jīng)排好序的鏈表合并成一個(gè)有序鏈表。為了方便操作，使用了一個(gè)虛擬頭節(jié)點(diǎn)dummy，然后再遍歷左右兩個(gè)鏈表，根據(jù)節(jié)點(diǎn)值的大小關(guān)系將節(jié)點(diǎn)插入到新的鏈表中。最后要注意，當(dāng)某一個(gè)鏈表已經(jīng)遍歷完時(shí)，要將另一個(gè)鏈表的剩余節(jié)點(diǎn)全部插入到新的鏈表中。

總之，這段代碼實(shí)現(xiàn)了對(duì)鏈表進(jìn)行排序的功能，采用了歸并排序的方法，是一個(gè)比較高效的算法。