147-链表插入排序

LeetCode 147. Insertion Sort List

LeetCode-147

Given the head of a singly linked list, sort the list using insertion sort, and return the sorted list’s head.

Input: head = [4,2,1,3]
Output: [1,2,3,4]

method:

head指向要插入的元素，pre遍历已排序的链表，找到小于head->val的最大值或者最末尾的元素，插入head

插入分两步：

1. head的next指向pre的next
2. pre的next指向head

ListNode* insertionSortList(ListNode* head) {
    ListNode *dummy = new ListNode(0);
    ListNode *pre = dummy;
    while (head) {
        ListNode *tmp = head->next;
        while (pre->next && pre->next->val < head->val) 
            pre = pre->next;
        head->next = pre->next; // 1
        pre->next = head;       // 2
        head = tmp;     // head回到原来的链表
        pre = dummy;    // pre回到开头
    }
    return dummy->next;
}