对链表进行插入排序
对链表进行插入排序。
插入排序的动画演示如上。从第一个元素开始，该链表可以被认为已经部分排序（用黑色表示）。 每次迭代时，从输入数据中移除一个元素（用红色表示），并原地将其插入到已排好序的链表中。
插入排序算法：
插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。 每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。 重复直到所有输入数据插入完为止。
示例:
输入: 4->2->1->3
输出: 1->2->3->4
思路
解法一：
- 使用虚拟头结点，便于在 head 节点前插入节点；
- 使用 last 指针维护已排序链表的最后一个节点， 使用 cur 指针指向待插入的元素；
- 比较 last 和 cur 的节点值
- 若 last -> val 小于 cur -> val，则两个指针位置不变，分别移动一位；
- 否则，使用 prev 指针找到插入 cur 位置的前一个节点
last->next = cur->next;
cur->next = prev->next;
prev->next = cur;
class Solution {
public:
ListNode* insertionSortList(ListNode* head) {
if (head == nullptr) {
return head;
}
ListNode *dumpyNode = new ListNode(0);
dumpyNode->next = head;
ListNode* last = head;
ListNode* cur = head->next;
while (cur != nullptr) {
if (last->val <= cur->next) {
last = last->val;
}else {
ListNode *prev = dumpyNode;
while (prev->next->val <= cur->val) {
prev = prev->next;
}
last->next = cur->next;
cur->next = prev->next;
prev->next = cur;
}
cur = last->next;
}
return dumpyNode->next;
}
};