From 7eee5a78005a9a569186d2c8b4b645a818ab9bf1 Mon Sep 17 00:00:00 2001 From: Stoycho Kyosev Date: Sun, 6 Oct 2024 07:04:44 -0400 Subject: Cleanup --- Seminar04/reorder-linked-list.cpp | 160 -------------------------------------- 1 file changed, 160 deletions(-) delete mode 100644 Seminar04/reorder-linked-list.cpp (limited to 'Seminar04/reorder-linked-list.cpp') diff --git a/Seminar04/reorder-linked-list.cpp b/Seminar04/reorder-linked-list.cpp deleted file mode 100644 index 6259a36..0000000 --- a/Seminar04/reorder-linked-list.cpp +++ /dev/null @@ -1,160 +0,0 @@ -#include"linked-list-utils.h" -#include - -// O(n) time -// O(n) complexity -void reorderWithDeque(LinkedListNode* head) { - if(!head || !head->next) - return; - - std::deque*> dq; - - LinkedListNode* it = head; - - while(it) { - dq.push_back(it); - it = it->next; - } - - // Винаги пазим края на вече готовия списък - // Ако не е ясно как го използвам прочети обяснението над втория метод - // идеята е същата. - LinkedListNode* 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 -void reverseLinkedList(LinkedListNode*& ll) { - LinkedListNode* previous = nullptr; - LinkedListNode* next = nullptr; - LinkedListNode* iterate = ll; - - while(iterate) { - next = iterate->next; - iterate->next = previous; - previous = iterate; - iterate = next; - } - - ll = previous; -} - -// Това също -template -LinkedListNode* findMiddle(LinkedListNode* ll) { - LinkedListNode* fast = ll; - LinkedListNode* 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* ll) { - if(!ll || !ll->next) - return; - - LinkedListNode* mid = findMiddle(ll); - reverseLinkedList(mid); - - LinkedListNode* firstHalf = ll; - LinkedListNode* currentPair = nullptr; - LinkedListNode* 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* ll = new LinkedListNode - (1, new LinkedListNode - (2, new LinkedListNode - (3, new LinkedListNode - (4, new LinkedListNode - (5))))); - - reorderWithTwoPointers(ll); - printLinkedList(ll); - freeList(ll); -} \ No newline at end of file -- cgit v1.3.1-26-gb76a