對鏈表進行插入排序，
插入排序的影片演示如上，從第一個元素開始，該鏈表可以被認為已經部分排序（用黑色表示），
每次迭代時，從輸入資料中移除一個元素（用紅色表示），并原地將其插入到已排好序的鏈表中，
插入排序演算法：
插入排序是迭代的，每次只移動一個元素，直到所有元素可以形成一個有序的輸出串列，
每次迭代中，插入排序只從輸入資料中移除一個待排序的元素，找到它在序列中適當的位置，并將其插入，
重復直到所有輸入資料插入完為止，
示例 1：
輸入: 4->2->1->3
輸出: 1->2->3->4
示例 2：
輸入: -1->5->3->4->0
輸出: -1->0->3->4->5
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/insertion-sort-list
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，
解題思路：
如果你還在為表頭的位置煩惱的話話，不如直接把表頭固定下來，然后順著表頭遍歷就行，注釋已經很詳細了，詳情見代碼如下：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* insertionSortList(ListNode* head) {
// 定義一個-1的表頭，這樣表頭永遠是-1
ListNode* first = new ListNode(-1);
// 遍歷head
while(head){
// 指向表頭的指標
ListNode* top = first;
// 找到比head大的位置
while(top -> next && top -> next -> val < head -> val){
top = top -> next;
}
// 經典指標交換操作
ListNode* index = head;
head = head -> next;
index -> next = top -> next;
top -> next = index;
}
return first -> next;
}
};
/*作者：heroding
鏈接：https://leetcode-cn.com/problems/insertion-sort-list/solution/yi-ge-biao-tou-jie-qian-chou-by-heroding/
來源：力扣（LeetCode）
著作權歸作者所有，商業轉載請聯系作者獲得授權，非商業轉載請注明出處，*/
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/225922.html
標籤：其他