对链表进行插入排序,
从链表第一个元素开始可以视为部分已排序,每次操作从链表中移除一个元素,然后原地将移除的元素插入到已排好序的部分。
数据范围:链表长度满足 ,链表中每个元素满足
例如输入{2,4,1}时,对应的返回值为{1,2,4},转换过程如下图所示:
struct ListNode* insertionSortList(struct ListNode* head ) { if(head==NULL) return NULL; struct ListNode *dummy = (struct ListNode*)malloc(sizeof(struct ListNode)); dummy->next = head; struct ListNode *p = dummy->next->next; struct ListNode *q = dummy; struct ListNode *cur = dummy->next; while(p!=NULL) { while(q->next!=p) { if(q->next->val>p->val) { cur->next = p->next; p->next = q->next; q->next = p; break; } q = q->next; } cur = p; p = p->next; q = dummy; } return dummy->next; }