#include "linked-list-utils.h" #define LLN LinkedListNode #include // Ex1 template void insertBeg(LLN*& head, const T& elem) { head = new LLN(elem, head); } void ex1() { LLN* head = new LLN(2, new LLN(3, new LLN(4))); printLinkedList(head); insertBeg(head, 1); printLinkedList(head); freeList(head); } // Ex 2 template void reverse(LLN*& head) { LLN* newHead = nullptr; LLN* iter; while (head != nullptr) { iter = head->next; head->next = newHead; newHead = head; head = iter; } head = newHead; } void ex2() { LLN* head = new LLN(1, new LLN(2, new LLN(3, new LLN(4, new LLN(5))))); printLinkedList(head); reverse(head); printLinkedList(head); freeList(head); } // Ex 3 template LLN* inefficientMiddle(LLN* head) { std::deque*> ptrs; while (head != nullptr) { ptrs.push_back(head); head = head->next; } while (ptrs.size() > 2) { ptrs.pop_front(); ptrs.pop_back(); } return ptrs.front(); } template LLN* middle(LLN* head) { LLN* fast = head, *slow = head; while (fast && fast->next) { fast = fast->next->next; slow = slow->next; } return slow; } void ex3() { LLN* head1 = new LLN(1, new LLN(2, new LLN(3, new LLN(4, new LLN(5))))); printLinkedList(head1); LLN* head2 = new LLN(1, new LLN(2, new LLN(3, new LLN(4)))); printLinkedList(head2); std::cout << middle(head1)->data << std::endl; std::cout << middle(head2)->data << std::endl; freeList(head1); freeList(head2); } // Ex4 template void reorder(LLN*& head) { if (!head) return; LLN* iter = head, *plast = head, *tail = head; while (iter->next != nullptr && iter->next->next != nullptr) { plast = iter; iter = iter->next; while (plast->next->next != nullptr) plast = plast->next; tail->next = plast->next; tail->next->next = iter; tail = tail->next->next; plast->next = nullptr; } } void ex4() { LLN* head = new LLN(1, new LLN(2, new LLN(3, new LLN(4, new LLN(5))))); printLinkedList(head); reorder(head); printLinkedList(head); freeList(head); head = new LLN(1, new LLN(2, new LLN(3, new LLN(4, new LLN(5, new LLN(6)))))); printLinkedList(head); reorder(head); printLinkedList(head); freeList(head); head = new LLN(1); printLinkedList(head); reorder(head); printLinkedList(head); freeList(head); head = nullptr; printLinkedList(head); reorder(head); printLinkedList(head); freeList(head); } int main() { ex4(); }