给老外做兼职的网站郑州搜狗关键词优化顾问

147. 对链表进行插入排序 - 力扣（LeetCode）

增加dummy方便判断，思路就是从前往后找，直到找到插入位置（注意需要知道插入位置的前驱才能进行插入，所以判断插入位置的时候是对tmp的next进行比较。）

双指针pre, cur一个用来定位已排序区间右边界，一个即为当前处理元素。

插入的逻辑为： 当前节点处断开，插入位置处也要断开，所以要注意两处断层的处理。

class Solution {
public:ListNode* insertionSortList(ListNode* head) {if(!head || !head->next)    return head;ListNode *dummy = new ListNode;dummy->next = head; //哨兵ListNode *pre = head;ListNode *cur = head->next;while(cur){auto tmp = dummy; if(pre->val > cur->val){while(tmp->next->val < cur->val)tmp = tmp->next;pre->next  = cur->next;cur->next = tmp->next;tmp->next = cur;cur = pre->next;}else{pre = pre->next;cur = cur->next;}}head = dummy->next;delete dummy;return head;}
};