阅读量:3
给你链表的头结点head，请将其按升序排列并返回排序后的链表。
示例 1：
输入：head = [4,2,1,3] 输出：[1,2,3,4]
示例 2：
输入：head = [-1,5,3,4,0] 输出：[-1,0,3,4,5]
示例 3：
输入：head = [] 输出：[]
提示：
- 链表中节点的数目在范围
[0, 5 * 104]内 -105<= Node.val <= 105
方法一：插入排序，但是由于链表是无序的，插入排序在最坏情况下的时间复杂度是 O(n^2)，这对于较大的输入会导致超时
插入排序思想，依次对未排序的节点插入到已经有序的链表中
#include<iostream> #include<math.h> using namespace std; struct ListNode{ int val; ListNode*next; ListNode(int x):val(x),next(NULL){} }; void create(ListNode* head){ int n=300; // cin>>n; ListNode* p=head; int a=2; for(int i=0;i<n;i++){ // cin>>a; ListNode* temp=new ListNode(a++); p->next=temp; p=p->next; } ListNode* temp=new ListNode(1); p->next=temp; p=p->next; } void print(ListNode* head){ ListNode* p=head; while(p!=NULL){ cout<<p-&