[插入排序]leetcode147：对链表进行插入排序(medium)

题目：web

147. 对链表进行插入排序svg

题解：spa

• 插入排序
• 注意对于这种打乱链表顺序的题，咱们通常都要设置哑节点dummy。
• 思路：咱们每次用head->next来进行插入排序，每次插入排序，咱们须要从链表的头部开始寻找插入点，因此咱们使用一个指针pre来寻找插入点，若pre->next的节点值大于等于head->next的节点时，咱们的插入位置就是pre->next，这里处理起来可能麻烦点，你们仔细看代码便可。

代码以下：指针

class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        //dummy用来设置哑节点，pre每次从表头开始进行插入排序
        ListNode* dummy=new ListNode(0),*pre;
        dummy->next=head;

        while(head&&head->next)//注意：咱们每次是将head的next节点进行插入排序的
        {
            if(head->val<=head->next->val){//head的next节点值大于等于head的节点值，表示这次不须要进行插入排序，进行下一次循环
                head=head->next;
                continue;
            }
            pre=dummy;
            //寻找插入的位置，pre的next节点值大于等于head的next节点值时，那么pre的next节点就是咱们的插入位置
            while(pre->next->val<head->next->val)pre=pre->next;

            //将head的next节点插入到pre的next上
            ListNode *cur=head->next;
            head->next=cur->next;//head链接cur节点后面的链表部分
            cur->next=pre->next;//cur链接pre的next节点，这样链表的顺序已经排好了，且链表仍是完整的
            pre->next=cur;
        } 

        return dummy->next;
    }
};