LeetCode Algorithm 147. 对链表进行插入排序

题目链接：147. 对链表进行插入排序

算法：插入排序
数据结构：链表
思路：定义一个lastSorted指针指向最后一个排好序的节点，再定义一个cur指针指向当前正在进行判断的节点，如果最后一个排好序的节点值小于当前正在判断的节点值，那么lastSorted指针和cur指针后移即可，否则说明需要将当前节点往前插入，首先定义一个pre节点指向头节点，如果pre的下一个节点值大于cur的节点值，那么就要把cur插入到pre节点的后方即可。

class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        if (head == nullptr) {
            return head;
        }

        ListNode *dummyHead = new ListNode(0);
        dummyHead->next = head;
        ListNode *lastSorted = head, *cur = head->next;
        while (cur != nullptr) {
            if (lastSorted->val <= cur->val) {
                lastSorted = lastSorted->next;
            } else {
                ListNode *pre = dummyHead;
                while (pre->next->val <= cur->val) {
                    pre = pre->next;
                }
                lastSorted->next = cur->next;
                cur->next = pre->next;
                pre->next = cur;
            }
            cur = lastSorted->next;
        }
        return dummyHead->next;
    }
};