链表-对链表进行插入排序
题目链接
插入排序的基本思想是，维护一个有序序列，初始时有序序列只有一个元素，每次将一个新的元素插入到有序序列中，将有序序列的长度增加 1，直到全部元素都加入到有序序列中。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| struct ListNode* insertionSortList(struct ListNode* head){
typedef struct ListNode ListNode;
ListNode* dummyNode = (ListNode*)malloc(sizeof(ListNode));
dummyNode->next = head;
ListNode* cur = head->next;
ListNode* LastStored = head;
while(cur){
if(cur->val >= LastStored->val)LastStored = LastStored->next;
else{
ListNode* prev = dummyNode;
while(prev->next->val <= cur->val)prev = prev->next;
LastStored->next = cur->next;
cur->next = prev->next;
prev->next = cur;
}
cur = LastStored->next;
}
return dummyNode->next;
}
|