Sort a linked list using insertion sort.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42 |
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */class
Solution {public: ListNode *insertionSortList(ListNode *head) { if(head==NULL || head->next==NULL) return
head; ListNode *root = new
ListNode(-INT_MAX); root->next = head; ListNode *pre = head; head = head->next; while(head){ ListNode *insert = root; while(insert != head&& insert->next->val <= head->val) insert = insert->next; if(insert==head){ pre = head; head = head->next; } else{ ListNode *tmp = insert->next; insert->next = head; pre->next = head->next; head->next = tmp; head = pre->next; } } head = root->next; delete
root; return
head; }}; |
插入排序，写一下数组的插入排序：
|
1
2
3
4
5
6
7
8
9
10 |
void
insertionSort(vector<int> &vec){ for(int
i = 1; i < vec.size();++i){ int
key = vec[i]; int
j = i - 1; for(; j>=0&&vec[j]>key; --j){ vec[j+1] = vec[j]; } vec[j+1]=key; } } |
Insertion Sort List,布布扣,bubuko.com
原文：http://www.cnblogs.com/nnoth/p/3767262.html