forked from shijbian/LeetCode
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathinsertion-sort-list.cpp
More file actions
100 lines (91 loc) · 2.25 KB
/
Copy pathinsertion-sort-list.cpp
File metadata and controls
100 lines (91 loc) · 2.25 KB
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
// Time: O(n^2)
// Space: O(1)
/**
* 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) {
ListNode dummy{numeric_limits<int>::min()};
auto curr = head;
ListNode *position = nullptr;
while (curr) {
position = findInsertPosition(&dummy, curr->val);
ListNode *tmp = curr->next;
curr->next = position->next;
position->next = curr;
curr = tmp;
}
return dummy.next;
}
ListNode* findInsertPosition(ListNode *head, int x) {
ListNode *prev = nullptr;
for (auto curr = head; curr && curr->val <= x;
prev = curr, curr = curr->next);
return prev;
}
};
// -----JF-----
/**
* 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) {
ListNode *res = NULL;
while (head) {
ListNode **p = &res;
ListNode *next = head->next;
while (*p && (*p)->val < head->val) p = &((*p)->next);
head->next = *p;
*p = head;
head = next;
}
return res;
}
};
//---------
/**
* 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) {
ListNode *res = NULL;
while (true) {
if (!head) break;
ListNode *next = head->next;
head->next = NULL;
if (!res) res = head;
else if (res->val > head->val) {
head->next = res;
res = head;
} else {
ListNode *current;
for (current = res; current->next && current->next->val < head->val; current = current->next);
if (!current->next) current->next = head;
else {
head->next = current->next;
current->next = head;
}
}
head = next;
}
return res;
}
};