Llist-Header

#ifndef LINKEDLIST_H_INCLUDED
#define LINKEDLIST_H_INCLUDED
#include <stack>
using namespace std;

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

int sizell(Node* head)
{
    int cnt = 0;
    Node* current = head;
    while (current != nullptr)
    {
        cnt++;
        current = current->next;
    }
    return cnt;
}

bool contains(Node* head, int el)
{
    Node* current = head;
    while(current != nullptr)
    {
        if (current->data == el)
        {
            return true;
        }
        current = current->next;
    }
    return false;
}

int GetNth(Node* head, unsigned index)
{
    if (sizell(head) < index)
    {
        throw "Index out of range exception!";
    }
    Node* current = head;
    for (int i = 0; i < index; i++)
    {
        current = current->next;
    }
    return current->data;
}

void InsertNth(Node*& head, unsigned index, int element)
{
    Node* n = new Node();
    n->data = element;
    if (head == nullptr || index == 0)
    {
        n->next = head;
        head = n;
    }
    else
    {
        Node* current = head;
        for (int i = 1; i < index && current->next != nullptr; i++)
        {
             current = current->next;
        }
        n->next = current->next;
        current->next = n;
    }
}

void DeleteNth(Node*& head, unsigned index)
{
    if (index >= sizell(head))
    {
        throw "Index out of range exception!";
    }
    if (index == 0)
    {
        Node* todelete = head;
        head = head->next;
        delete todelete;
        return;
    }
    Node* current = head;
    Node* prev;
    for (int i = 0; i < index; i++)
    {
        prev = current;
        current = current->next;
    }
    prev->next = current->next;
    delete current;
}

void DeleteList(Node*& head)
{
    Node* current = head;
    Node* todelete;
    while (current != nullptr)
    {
        todelete = current;
        current = current->next;
        delete todelete;
    }
    head = nullptr;
}

void printList(Node* head)
{
    Node* current = head;
    while (current != nullptr)
    {
        cout << current->data << " ";
        current = current->next;
    }
    cout << endl;
}

Node* CopyList(Node*& head)
{
    Node* copyl = nullptr;
    for (int i = 0; i < sizell(head); i++)
    {
        InsertNth(copyl, i, GetNth(head, i));
    }
    return copyl;
}

void Append(Node*& a, Node*& b)
{
    int sizea = sizell(a);
    int sizeb = sizell(b);
    for (int i = 0; i < sizeb; i++)
    {
        InsertNth(a, sizea+i, GetNth(b, i));
    }
    b = nullptr;
}

Node* SortedMerge(Node* a, Node* b)
{
    Node dummy;
    dummy.next = nullptr;
    Node* tail = &dummy;

    while (true)
    {
        if (a == nullptr)
        {
            tail->next = b;
            break;
        }
        if (b == nullptr)
        {
            tail->next = a;
            break;
        }
        if (a->data < b->data)
        {
            tail->next = a;
            tail = a;
            a=a->next;
        }
        else
        {
            tail->next = b;
            tail = b;
            b=b->next;
        }
    }
    return dummy.next;
}

void FrontBackSplit(Node* head, Node*& front, Node*& back)
{
    if (head == nullptr)
    {
        front = nullptr;
        back = nullptr;
    }
    else
    {
        Node* slowptr = head;
        Node *fastptr = head->next;
        while (fastptr != nullptr)
        {
            fastptr = fastptr->next;
            if (fastptr != nullptr)
            {
                fastptr = fastptr->next;
                slowptr = slowptr->next;
            }
        }
        back = slowptr->next;
        slowptr->next = nullptr;
        front = head;
    }
}

void RemoveDublicates(Node*& head)
{
    if (head == nullptr)
    {
        return;
    }
    Node *current = head;
    while (current->next != nullptr)
    {
        if (current->data == current->next->data)
        {
            Node* todelete = current->next;
            current->next = current->next->next;
            delete todelete;
        }
        else
        {
            current = current->next;
        }
    }
}

void MergeSort(Node*& head)
{
    if (head == nullptr || head->next == nullptr)
    {
        return;
    }
    Node* front;
    Node* back;
    FrontBackSplit(head, front, back);
    MergeSort(front);
    MergeSort(back);
    head = SortedMerge(front, back);
}

void MoveNode(Node*& a, Node*& b)
{
    if (b == nullptr)
    {
        return;
    }
    Node* temp = b->next;
    b->next = a;
    a = b;
    b = temp;
}

void AlternatingSplit(Node* head, Node*& a, Node*& b)
{
    a = nullptr;
    b = nullptr;
    if (head == nullptr)
    {
        return;
    }
    while (true)
    {
        if (head != nullptr)
        {
           MoveNode(a, head);
        }
        else
        {
            break;
        }
        if (head != nullptr)
        {
           MoveNode(b, head);
        }
        else
        {
            break;
        }
    }
}

void AlternatingSplit2(Node* head, Node*& a, Node*& b)
{
    a = nullptr;
    b = nullptr;
    if (head == nullptr)
    {
        return;
    }
    int i = 0;
    Node* current = head;
    while (true)
    {
        if (current != nullptr)
        {
            InsertNth(a, i, current->data);
        }
        else
        {
            break;
        }
        current = current->next;
        if (current != nullptr)
        {
            InsertNth(b, i, current->data);
        }
        else
        {
            break;
        }
        current = current->next;
        i++;
    }
}

void PushBack(Node*& head, int element)
{
    InsertNth(head, sizell(head), element);
}

Node* ShuffleMerge(Node* a, Node* b)
{
    Node* result = nullptr;
    Node* currentA = a;
    Node* currentB = b;
    while (true)
    {
        if (currentA != nullptr)
        {
            PushBack(result, currentA->data);
            currentA = currentA->next;
        }
        if (currentB != nullptr)
        {
            PushBack(result, currentB->data);
            currentB = currentB->next;
        }
        if (currentA == nullptr && currentB == nullptr)
        {
            break;
        }
    }
    return result;
}

void Shuffle(Node*& head)
{
    Node* a;
    Node* b;
    FrontBackSplit(head, a, b);
    head = ShuffleMerge(a, b);
}

Node* SortedUnion(Node* a, Node* b)
{
    Node* unionl = SortedMerge(a, b);
    RemoveDublicates(unionl);
    return unionl;
}

Node* SortedIntersectSortedUnion(Node* a, Node* b)
{
    Node* intersect = nullptr;
    Node* current = a;
    while (current != nullptr)
    {
        if (contains(b, current->data) && !contains(intersect, current->data))
        {
            PushBack(intersect, current->data);
        }
        current = current->next;
    }
    return intersect;
}

Node* SortedDifference(Node* a, Node* b)
{
    Node* diff = nullptr;
    Node* current = a;
    while (current != nullptr)
    {
        if (!contains(b, current->data) && !contains(diff, current->data))
        {
            PushBack(diff, current->data);
        }
        current = current->next;
    }
    return diff;
}

void Reverse(Node*& head)
{
    Node* previous = nullptr;
    Node* current = head;
    Node* next;
    while (current != nullptr)
    {
        next = current->next;
        current->next = previous;
        previous = current;
        current = next;
    }
    head = previous;
}

void ReverseWithStack(Node*& head)
{
    stack<int> st;
    Node* current = head;
    while (current != nullptr)
    {
        st.push(current->data);
        current = current->next;
    }
    current = head;
    while (current != nullptr)
    {
        current->data = st.top();
        st.pop();
        current = current->next;
    }
}

#endif // LINKEDLIST_H_INCLUDED