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
101
102
103
104
105
106
107
108
109
110
111
112
|
#include <iostream>
struct ListNode
{
int val;
ListNode* next;
ListNode(int x, ListNode* next = nullptr) : val(x), next(next) {}
};
template<class Comparator>
void insert_sorted(ListNode*& head, ListNode*& tail, ListNode* element, const Comparator& cmp)
{
if(head == nullptr)
{
head = tail = element;
return;
}
if(!cmp(head->val, element->val))
{
element->next = head;
head = element;
return;
}
ListNode* iter = head;
while(iter->next)
{
if(!cmp(iter->next->val, element->val))
break;
iter = iter->next;
}
if(iter->next == nullptr)
tail = element;
element->next = iter->next;
iter->next = element;
}
ListNode* odd_even_sort(ListNode* node)
{
if(!node || !node->next)
return node;
ListNode* even_head = nullptr;
ListNode* even_tail = nullptr;
ListNode* odd_head = nullptr;
ListNode* odd_tail = nullptr;
std::less<int> less;
std::greater<int> greater;
while(node)
{
ListNode* to_insert = node;
node = node->next;
to_insert->next = nullptr;
if(to_insert->val % 2 == 0)
{
insert_sorted(even_head, even_tail, to_insert, less);
}
else
{
insert_sorted(odd_head, odd_tail, to_insert, greater);
}
}
if(odd_tail != nullptr)
odd_tail->next = nullptr;
if(even_head == nullptr)
{
return odd_head;
}
even_tail->next = odd_head;
return even_head;
}
void free_list(ListNode* list)
{
while(list)
{
ListNode* to_delete = list;
list = list->next;
delete list;
}
}
int main()
{
ListNode* example = new ListNode(
11, new ListNode(21, new ListNode(31, new ListNode(5, new ListNode(51))))
);
ListNode* result = odd_even_sort(example);
ListNode* iter = result;
while(iter)
{
std::cout << iter->val << " ";
iter = iter->next;
}
free_list(result);
}
|
