class Solution {
public:
ListNode* insertionSortList(ListNode* head) {
if (head == nullptr || head->next == nullptr) {
return head;
}
ListNode* start = head; // 表头
ListNode* end = head; // 表尾
ListNode* p = end->next; // 待排序
while (p) { // 遍历
if (start->val >= p->val) { // 插到表头
end->next = p->next;
p->next = start;//p和start交换
start = p;
}
else if (end->val <= p->val) { // 插入表尾
end = p;
}
else { // 插入表中
end->next = p->next;
ListNode* temp = start;
while(temp->next->val < p->val) {//遍历
temp = temp->next;
}
p->next = temp->next;//p和t->next交换
temp->next = p;
}
p = end->next;
}
return start;
}
};
