LeetCode | Insertion Sort List

https://leetcode.com/problems/insertion-sort-list/

链表的插入排序。实现起来有不少细节须要仔细考虑。

class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        if (!head || !head->next) return head;
        
        ListNode dummy(0); dummy.next = head;
        head = head->next;
        ListNode *pre = dummy.next;
        while (head) {
            ListNode *p = &dummy, *next = head->next;
            while (p->next != head && p->next->val <= head->val) {
                p = p->next;
            }
            if (p->next->val > head->val) {
                pre->next = head->next;
                head->next = p->next;
                p->next = head;
            } else pre = pre->next;  // 这句很关键。仔细想想，如果当前节点变动了，pre就不用更新
            
            head = next;
        }
        
        return dummy.next;
    }
};