對鏈表進(jìn)行插入排序

題目描述：對鏈表進(jìn)行插入排序。

插入排序的動畫演示如上。從第一個元素開始，該鏈表可以被認(rèn)為已經(jīng)部分排序（用黑色表示）。 每次迭代時，從輸入數(shù)據(jù)中移除一個元素（用紅色表示），并原地將其插入到已排好序的鏈表中。

插入排序算法：

• 插入排序是迭代的，每次只移動一個元素，直到所有元素可以形成一個有序的輸出列表。

• 每次迭代中，插入排序只從輸入數(shù)據(jù)中移除一個待排序的元素，找到它在序列中適當(dāng)?shù)奈恢茫⑵洳迦搿?/p>

• 重復(fù)直到所有輸入數(shù)據(jù)插入完為止。

示例說明請見LeetCode官網(wǎng)。

來源：力扣（LeetCode） ??

鏈接：https://leetcode-cn.com/problems/insertion-sort-list/ ??

著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

解法一：鏈表遍歷

• 首先，如果鏈表為空或者鏈表只有一個節(jié)點，則不用排序，直接返回。

• 否則，使用插入排序的方式將鏈表中的節(jié)點都放到一個List中nodes；

• 然后，按照nodes的順序重新構(gòu)造一個新的鏈表即為排序后的鏈表，返回之。

【每日寄語】 每個人的人生軌跡恐怕都是事先命定的，但是你得努力，并相信命運是掌握在自己手中的，人不怕有理想，不怕這個理想有多高多遠(yuǎn)多大，只要堅持，不過分高估自己，總會成功。