-
Notifications
You must be signed in to change notification settings - Fork 0
/
sort-circular-doubly.c
89 lines (78 loc) · 1.73 KB
/
sort-circular-doubly.c
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
#include "sort-list.h"
struct __list {
int data;
struct __list *prev, *next;
};
list *sort(list *start)
{
if (!start || start->next == start->prev)
return start;
list *left = start;
list *right = left->next;
right->prev = left->prev;
right->prev->next = right;
left->prev = left;
left->next = left;
left = sort(left);
right = sort(right);
left->prev->next = NULL;
right->prev->next = NULL;
list *merge;
for (merge = NULL; left || right;) {
if (!right || (left && left->data < right->data)) {
if (!merge) {
start = merge = left;
} else {
merge->next = left;
merge->next->prev = merge;
merge = merge->next;
}
left = left->next;
} else {
if (!merge) {
start = merge = right;
} else {
merge->next = right;
merge->next->prev = merge;
merge = merge->next;
}
right = right->next;
}
}
merge->next = start;
start->prev = merge;
return start;
}
void insert_node(list **l, int d)
{
list *tmp = malloc(sizeof(list));
tmp->data = d;
if (!(*l)) {
tmp->prev = tmp;
tmp->next = tmp;
} else {
tmp->prev = *l;
tmp->next = (*l)->next;
(*l)->next->prev = tmp;
(*l)->next = tmp;
}
*l = tmp;
}
void delete_list(list *l)
{
l->prev->next = NULL;
list *tmp;
while (l) {
tmp = l->next;
free(l);
l = tmp;
}
}
void print_list(list *l)
{
list *tmp = l;
while (tmp != l) {
printf("%d\n", tmp->data);
tmp = tmp->next;
}
}