blob: 6259a36cae3f64eb6a93fd68fbf533211f7b39ae (
plain) (
blame)
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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
|
#include"linked-list-utils.h"
#include<deque>
// O(n) time
// O(n) complexity
void reorderWithDeque(LinkedListNode<int>* head) {
if(!head || !head->next)
return;
std::deque<LinkedListNode<int>*> dq;
LinkedListNode<int>* it = head;
while(it) {
dq.push_back(it);
it = it->next;
}
// Винаги пазим края на вече готовия списък
// Ако не е ясно как го използвам прочети обяснението над втория метод
// идеята е същата.
LinkedListNode<int>* backOfNewList = nullptr;
while(!dq.empty()) {
// Ако размерът е 1 то имаме нечетен брой елементи и просто добавяме последния в края
if(dq.size() == 1) {
backOfNewList->next = dq.front();
backOfNewList = backOfNewList->next;
break;
}
// Първия елемент останал в дека започва да сочи към последния.
// Генерираме коректна двойка.
dq.front()->next = dq.back();
// Ако края на списъка не е nullptr следващите два елемента
// в списъка са dq.front()->dq.front()->next (което е dq.back())
if(backOfNewList)
backOfNewList->next = dq.front(); // Сложи следващите два елемента накрая
backOfNewList = dq.front()->next; // Вече края на списъка е друг. Преместваме се там.
dq.pop_back();
dq.pop_front();
}
// next на последния елемент от списъка е nullptr, този ред е важен.
backOfNewList->next = nullptr;
}
// Това ще ни помогне за второто решение
template<class T>
void reverseLinkedList(LinkedListNode<T>*& ll) {
LinkedListNode<T>* previous = nullptr;
LinkedListNode<T>* next = nullptr;
LinkedListNode<T>* iterate = ll;
while(iterate) {
next = iterate->next;
iterate->next = previous;
previous = iterate;
iterate = next;
}
ll = previous;
}
// Това също
template<class T>
LinkedListNode<T>* findMiddle(LinkedListNode<T>* ll) {
LinkedListNode<T>* fast = ll;
LinkedListNode<T>* slow = ll;
while(fast && fast->next) {
fast = fast->next->next;
slow = slow->next;
}
return slow;
}
/*
Тук идеята е да намерим средата и да я обърнем. Две неща, които вече знаем как да правим. Как ще протече алгоритъма:
Вход: 1 -> 2 -> 3 -> 4 -> 5
Среда: 3 -> 4 -> 5
Обърната среда: 5 -> 4 -> 3 -> nullptr
Как изглежда първоначалния масив: 1 -> 2 -> 3 -> nullptr
Дали е бъг, че и в двата списъка имаме еднакъв последен елемент? Малко неточно е, но за да го оправя трябва да променя функциите.
С цел да са разбираеми нещата го оставям така.
В случая става нещо подобно:
1-> 2 -> 3 -> nullptr
^
5 -> 4 /
Виждаме, че последователно трябва да вземаме двойки (L_0 -> L_n) -> (L_1 -> L_{n-1}) -> (L_2 -> L_{n - 2}) -> ... и да ги поставяме една след друга.
* firstHalf -> първата половина от списъка
* mid -> Втората половина от списъка
* currentPair -> текущата двойка (L_i -> L_{n - i})
* backOfList -> Края на коректния списък от двойки
Сега имаме този сценарий:
[някакъв коректен списък] [коректна двойка]
* Насочи края на този коректен списък да сочи към коректната двойка. Това става лесно понеже му пазя края!
[някакъв вече готов списък] -> [коректна двойка]
* Сега насочи указателя който пази края на коректния списък да сочи към края на този списък, понеже този списък е корекрен.
[стария коректен списък -> коректната двойка] - готов за още коректни двойки!
Така добавямe коректни двойки докато не стигна края на списъка съдържащ обърнатата дясна част.
*/
void reorderWithTwoPointers(LinkedListNode<int>* ll) {
if(!ll || !ll->next)
return;
LinkedListNode<int>* mid = findMiddle(ll);
reverseLinkedList(mid);
LinkedListNode<int>* firstHalf = ll;
LinkedListNode<int>* currentPair = nullptr;
LinkedListNode<int>* backOfList = nullptr;
while(mid) {
currentPair = firstHalf;
firstHalf = firstHalf->next;
// Случая в който имаме нечетен брой елементи
if(!firstHalf) {
backOfList->next = currentPair;
backOfList = backOfList->next;
break;
}
currentPair->next = mid;
mid = mid->next;
if(backOfList)
backOfList->next = currentPair; // Пренасочи края към коректната двойка. Ако е nullptr нямаме какво да пренасочваме.
backOfList = currentPair->next; // И един бърз ъпдейт на края - вече края на коректния лист е стария лист + новата двойка
}
backOfList->next = nullptr;
}
int main() {
LinkedListNode<int>* ll = new LinkedListNode<int>
(1, new LinkedListNode<int>
(2, new LinkedListNode<int>
(3, new LinkedListNode<int>
(4, new LinkedListNode<int>
(5)))));
reorderWithTwoPointers(ll);
printLinkedList(ll);
freeList(ll);
}
|
