task4

#include <iostream>
#include <vector>
#include <string>
#include <memory>
#include <cmath>

/*
Имеется простой односвязный список размера N. Необходимо реализовать алгоритм, который перепаковывает список так,
чтобы за первым элеметом следовал последний, затем второй, затем предпоследний и т. д.
Пример работы алгоритма:
исходный список: 1-2-3-4-5-6-7-8
перепакованный список: 1-8-2-7-3-6-4-5.
Оценить сложность предложенного алгоритма.
*/

class Node
{
public:
    int val;
    std::shared_ptr<Node> next;
    Node(int v) : val(v), next(nullptr) {};
};

class List
{
public:
    List():size(0), head(nullptr){};
    void add(int value);
    std::shared_ptr<Node> get_head();
    int get_size();

private:
    int size;
    std::shared_ptr<Node> head;
};

void
List::add(int value)
{
    if (head != nullptr){
        std::shared_ptr<Node> curr = head;
        while(curr->next != nullptr){
            curr = curr->next;
        }
        std::shared_ptr<Node> tmp_ptr(new Node(value));
        curr->next = tmp_ptr;
        size++;
    } else {
        std::shared_ptr<Node> tmp_ptr(new Node(value));
        head = tmp_ptr;
        size++;
    }
}

std::shared_ptr<Node>
repack(std::shared_ptr<Node> head, int size)
{
    if (size < 2){
        return head;
    }

    std::shared_ptr<Node> middle_ptr(head);
    bool is_odd = size % 2;
    int n = std::ceil(size / 2.0);
    for ( ;n > 1; n--, middle_ptr = middle_ptr->next);
    std::shared_ptr<Node> tmp_ptr(middle_ptr);
    middle_ptr = middle_ptr->next;
    tmp_ptr->next = nullptr;

    std::shared_ptr<Node> reverse_head(new Node(middle_ptr->val));
    middle_ptr = middle_ptr->next;
    while(middle_ptr != nullptr){
        tmp_ptr.reset(new Node(middle_ptr->val));
        tmp_ptr->next = reverse_head;
        reverse_head = tmp_ptr;
        middle_ptr = middle_ptr->next;
    }

    std::shared_ptr<Node> curr(head);
    tmp_ptr.reset();
    std::shared_ptr<Node> tmp_reverse_ptr;

    while(curr != nullptr && reverse_head != nullptr){
        tmp_ptr = curr->next;
        curr->next = reverse_head;
        tmp_reverse_ptr = reverse_head->next;
        reverse_head->next = tmp_ptr;
        curr = tmp_ptr;
        reverse_head = tmp_reverse_ptr;
    }

    if (is_odd){
        curr->next = nullptr;
    }

    return head;
}

std::shared_ptr<Node>
List::get_head()
{
    return head;
}

int
List::get_size()
{
    return size;
}

void print_list(std::shared_ptr<Node> head)
{
    std::shared_ptr<Node> curr(head);
    while(curr != nullptr){
        std::cout << curr->val << " ";
        curr = curr->next;
    }
    std::cout << std::endl;
}

int main(int argc, char** argv)
{
    List l;
    l.add(1);
    l.add(2);
    l.add(3);
    l.add(4);
    l.add(5);
    std::shared_ptr<Node> list_head = l.get_head();
    print_list(list_head);
    std::shared_ptr<Node> repack_list = repack(list_head, l.get_size());
    print_list(repack_list);
    return 0;
}