1. 題目

對鏈表進行插入排序。

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

插入排序算法：

插入排序是迭代的，每次只移動一個元素，直到所有元素可以形成一個有序的輸出列表。
每次迭代中，插入排序只從輸入數據中移除一個待排序的元素，找到它在序列中適當的位置，并將其插入。
重復直到所有輸入數據插入完為止。

示例 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
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

2.1 multimap 取巧做法

• 利用map的有序性，把節點指針存進去

class Solution { public:ListNode* insertionSortList(ListNode* head) {if(!head || !head->next)return head;ListNode *emptyHead = new ListNode(0);emptyHead->next = head;multimap<int, ListNode*> m;while(head){m.emplace(head->val, head);head = head->next;}head = emptyHead;for(auto & kv : m){head->next = kv.second;head = head->next; }head->next = NULL;return emptyHead->next;} };

2.2 鏈表做法

class Solution { public:ListNode* insertionSortList(ListNode* head) {if(!head || !head->next)return head;ListNode *emptyHead = new ListNode(0);emptyHead->next = head;ListNode *cur = head->next, *tail = head, *nt = NULL, *t, *prev;while(cur){nt = cur->next;//下一個待遍歷的元素if(cur->val >= tail->val)//大于已排序的結尾，直接接上尾巴{tail->next = cur;tail = cur;}else//小于結尾，從頭開始遍歷{prev = emptyHead;t = emptyHead->next;while(cur->val > t->val){prev = t;t = t->next;}prev->next = cur;cur->next = t;}cur = nt;}tail->next = NULL;//最后結尾指向NULLreturn emptyHead->next;} };

總結

以上是生活随笔為你收集整理的LeetCode 147. 对链表进行插入排序（链表）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。