题目描述

点这里

思路分析

链表+排序
插入排序，类似于整理扑克牌。每次把插入数插入到比他大的第一个数前边。

代码实现

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* insertionSortList(ListNode* head) {auto dummy=new ListNode(-1);for(auto p=head;p;){auto cur=dummy,ne=p->next;while(cur->next&&cur->next->val<=p->val) cur=cur->next;p->next=cur->next;cur->next=p;p=ne;}return dummy->next;}
};