/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) : val(x), next(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param head ListNode类
* @return ListNode类
*/
ListNode* insertionSortList(ListNode* head) {
// write code here
//遍历链表,找到下降的点,然后把下降的点插入到合适位置
if (head == NULL)return head;
ListNode* p = head;
while (p->next) {
while (p->next && p->next->val > p->val)p = p->next;
if (p->next == NULL) {
return head;
}
ListNode *tmp=p->next;//保存条件点
p->next=p->next->next;//原链表删除条件点
if(tmp->val<head->val){//插在头结点
tmp->next=head;
head=tmp;
}
else{//插在中间
ListNode *t=head;
while (t->next&&t->next->val<tmp->val) t=t->next;
tmp->next=t->next;
t->next=tmp;
}
}
return head;
}
};