SAA_Danny_Spisuk

#include <iostream>

using namespace std;

struct List
{
    int data;
    List *next;
};

auto push(List** head_ref, int new_data) -> void {
    List* new_list = new List;

    new_list->data = new_data;

    new_list->next = (*head_ref);

    (*head_ref) = new_list;
}

auto push_at_end(List** head_ref, int new_data) -> void {
    List* new_list = new List;

    List *last = *head_ref;

    new_list->data = new_data;

    new_list->next = nullptr;

    if (*head_ref == nullptr)
    {
        *head_ref = new_list;
        return;
    }

    while (last->next != nullptr)
        last = last->next;

    last->next = new_list;
    return;
}

auto printList(List *list) -> void {
    while (list != nullptr)
    {
        cout << list->data << "  ";
        list = list->next;
    }
}

// Задачката от Упражненията 7.1 -- Вариант с глобална променлива:
// Изкарваш size_t count = 0 извън функцията и пак ще бачка хехе
// Другото просто го местиш във main и тука пишеш auto count_of_elements(List *head, size_t &count) -> int и пак работи
auto count_of_elements(List* head) -> int {
    size_t count = 0;
    List* current = head;
    while (current != nullptr)
    {
        count++;
        current = current->next;
    }
    return count;
}

auto max_element(List* head) -> int
{
    // INT_MIN е -32767. Ползваме го за начална стойност на максималният елемент
    int max = INT_MIN;

    while (head != nullptr) {

        if (max < head->data)
            max = head->data;
        head = head->next;
    }
    return max;
}

auto most_occuring_element(List* head) -> int {
    List* p = head;

    int total_count = 0, max_count = 0, res = -1;
    while (p != nullptr) {

        int count = 1;
        List* q = p->next;
        while (q != nullptr) {
            if (p->data == q->data)
                count++;
            q = q->next;
        }

        if (count > max_count)
        {
            max_count = count;
            res = p->data;
        }

        p = p->next;
        total_count++;
    }

    if (max_count >= total_count / 2)
        return res;

    return -1; // Няма най-често срещан елемент, който да е над другите(тоест са по равно всичките)
}

auto delete_first(List **head_ref, List *del) -> void {
    /* base case */
    if (*head_ref == nullptr || del == nullptr)
        return;

    /* If node to be deleted is head node */
    if (*head_ref == del)
        *head_ref = del->next;

    /* Finally, free the memory occupied by del*/
    delete del;
    return;
}

auto remove_duplicates(List *start) -> void {
    List *ptr1, *ptr2, *dup;
    ptr1 = start;

    while (ptr1 != nullptr && ptr1->next != nullptr)
    {
        ptr2 = ptr1;

        while (ptr2->next != nullptr)
        {
            if (ptr1->data == ptr2->next->data)
            {
                dup = ptr2->next;
                ptr2->next = ptr2->next->next;
                delete(dup);
            }
            else
                ptr2 = ptr2->next;
        }
        ptr1 = ptr1->next;
    }
}

int main()
{
    List* list = nullptr;

    push_at_end(&list, 6);

    push(&list, 7);

    push(&list, 1);

    push_at_end(&list, 4);

    push(&list, 4);
    push(&list, 4);
    push_at_end(&list, 1);
    push(&list, 1);

    cout << "\nLinked list: ";
    printList(list);

    cout << "\n\nCount of elements: " << count_of_elements(list);
    cout << "\n\nMax element: " << max_element(list);

    if (most_occuring_element(list) != (-1))
        cout << "\n\nMost occuring element: " << most_occuring_element(list);
    else
        cout << "\n\nNo most occurring element!";

    cout << "\n\nLinked list without first element: ";
    delete_first(&list, list);
    printList(list);

    cout << "\n\nList with removed duplicates: ";
    remove_duplicates(list);
    printList(list);

    return 0;
}