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
|
#include <iostream>
template <typename T>
struct Node {
T value;
Node<T>* next;
Node(T value, Node<T>* next = nullptr) : value(value), next(next) {}
};
template <typename T, typename U>
struct Pair {
T left;
U right;
Pair(T left, U right) : left(left), right(right) {}
};
#define PII Pair<int, int>
#define NPII Node<Pair<int, int>*>
template <typename T>
void reverseSublist(Node<T>*& list, int start, int end) {
Node<T>* prev = nullptr; // element before first in range
Node<T>* iter = list; // first element in range
while (start > 0) {
prev = iter;
iter = iter->next;
start--;
end--;
}
Node<T>* eter = iter; // last element in range
Node<T>* next = nullptr; // element after last in range
for (int i = 0; i < end; i++) {
eter = eter->next;
next = eter->next;
}
prev->next = eter;
Node<T>* last;
Node<T>* prevLast;
while (end > 0) {
prevLast = iter;
last = iter->next;
for (int i = 1; i < end; i++) {
prevLast = prevLast->next;
last = last->next;
}
last->next = prevLast;
end--;
}
prevLast->next = next;
}
template <typename T>
void reverseSublists(Node<T>*& list, NPII* intervals) {
while (intervals != nullptr) {
reverseSublist(list, intervals->value->left, intervals->value->right);
intervals = intervals->next;
}
}
template <typename T>
void print(Node<T>* list) {
while (list != nullptr) {
std::cout << list->value << " ";
list = list->next;
}
std::cout << std::endl;
}
int main() {
NPII* intervals = new NPII(new PII(1, 3), new NPII(new PII(2, 5), new NPII(new PII(5, 6))));
Node<int>* list = new Node<int>(11, new Node<int>(4, new Node<int>(3, new Node<int>(7, new Node<int>(13, new Node<int>(4, new Node<int>(5)))))));
print(list);
reverseSublists(list, intervals);
print(list);
NPII* temp = nullptr;
while (intervals != nullptr) {
delete intervals->value;
temp = intervals->next;
delete intervals;
intervals = temp;
}
Node<int>* temp1 = nullptr;
while (list != nullptr) {
temp1 = list->next;
delete list;
list = temp1;
}
}
|
