對鏈表進行插入排序廉白。
image.png
插入排序的動畫演示如上隧饼。從第一個元素開始，該鏈表可以被認(rèn)為已經(jīng)部分排序（用黑色表示）助币。
每次迭代時浪听，從輸入數(shù)據(jù)中移除一個元素（用紅色表示），并原地將其插入到已排好序的鏈表中奠支。
插入排序算法：
1.插入排序是迭代的馋辈，每次只移動一個元素，直到所有元素可以形成一個有序的輸出列表倍谜。
2.每次迭代中迈螟，插入排序只從輸入數(shù)據(jù)中移除一個待排序的元素，找到它在序列中適當(dāng)?shù)奈恢枚蓿⑵洳迦搿?br>
3.重復(fù)直到所有輸入數(shù)據(jù)插入完為止答毫。
示例 1：
輸入: 4->2->1->3
輸出: 1->2->3->4
示例 2：
輸入: -1->5->3->4->0
輸出: -1->0->3->4->5
代碼
class Solution {
public:
ListNode* insertionSortList(ListNode* head) {
ListNode *dummy = new ListNode(-1), *cur = dummy;
while (head) {
ListNode *t = head->next;
cur = dummy;
while (cur->next && cur->next->val <= head->val) {
cur = cur->next;
}
head->next = cur->next;
cur->next = head;
head = t;
}
return dummy->next;
}
};
