spisok

#include<iostream>
using namespace std;



struct Node
{
    int item;
    Node *next;
};
Node* addHead(Node *head, int Value)
{
    Node *temp = new Node;

    temp->next = head;
    temp->item = Value;

    head = temp;
    return head;
}

Node* removeHead(Node  *head)
{
    if (head == NULL)
        return 0;

    Node *p = head;
    head = p->next;

    delete p;
    return head;
}

Node* findItem(Node *head, int Value)
{
    Node *p = head;

    while (p != NULL)
    {
        if (p->item == Value) return p;
        p = p->next;
    }

    return NULL;
}
Node* findPos(Node *head, int pos)
{
    Node *p = head;

    while ((p != NULL) && (pos > 1))
    {
        p = p->next;
        pos--;
    }

    if (p != NULL)
        return p;
    else
        return NULL;
}
void insertAfterItem(Node *p, int Value)
{
    if (p == NULL) return;

    Node *temp = new Node;

    temp->next = p->next;
    temp->item = Value;

    p->next = temp;
}
Node *insert(int number, Node *lst)
{
    Node *temp, *p;
    temp = new Node;
    p = lst->next;
    lst->next = temp;
    temp->item = number;
    temp->next = p;
    return(temp);
}
Node* remove(Node *head, Node *p)
{
    if ((head == NULL) || (p == NULL))  return head;
    if (head == p)
    {
        head = removeHead(head);
        return head;
    }

    Node *temp = head;

    while ((temp->next != NULL) && (temp->next != p))
        temp = temp->next;

    if (temp->next == NULL) return head;
    temp->next = p->next;
    delete p;
    return head;
}

void removeAll(Node *Head)
{
    Node *p = Head;
    Node *temp;
    if (p != NULL)
    {
        cout << "Список пустой...\n";
        return;
    }
    while (p != 0)
    {
        temp = p;
        p = p->next;
        delete(temp);
    }
}

void outList(Node *head)
{
    Node *p = head;
    while (p != NULL)
    {
        cout << p->item << " ";
        p = p->next;
    }
    cout << endl;
}

bool isEmpty(Node *l)
{
    return (l == NULL);
}

Node  *sortlists(Node *a, Node *b)
{
    Node *result, *tmp;
    if (a->item <= b->item)
    {
        result = a;
        a = a->next;
    }
    else
    {
        result = b;
        b = b->next;
    }
    tmp = result;
    while (a != NULL && b != NULL)
    {
        if (a->item <= b->item)
        {
            tmp->next = a;
            tmp = a;
            a = a->next;
        }
        else
        {
            tmp->next = b;
            tmp = b;
            b = b->next;
        }
    }
    if (a != NULL)
        tmp->next = a;
    else
        if (b != NULL)
            tmp->next = b;
    return result;
}
int menu()
{
    cout << "\n 1 : Добавить элементы \n";
    cout << " 2 : Вывести список \n";
    cout << " 3 : Вставить элемент после заданного\n";
    cout << " 4 : Вставить элемент в заданную позицию \n";
    cout << " 5 : Удалить заданный элемент \n";
    cout << " 6 : Удалить из головы\n";
    cout << " 7 : Проверка на пустосту\n";
    cout << " 8 : Удалить список\n";
    cout << " 9 : Объединить два упорядоченных списка\n";
    return 0;
}
int main()
{
    setlocale(LC_ALL, "Russian");
    Node *head = NULL;
    Node *p;
    Node *tail = NULL;
    Node *summ = NULL;
    int k;



    int ans;
    int val;
    do
    {
        menu();
        cout << " Выберете действие\n";

        cin >> (ans);
        switch (ans)
        {
        case 1: cout << "Введите элементы\nДля завершения введите 0\n";
            cin >> k;
            while (k != 0)
            {
                head = addHead(head, k);
                cin >> k;
            }

            break;
        case 2:
            outList(head);
            break;
        case 3:
            int val;
            cout << "Введите значение после которого будет добавлен элемент\n";
            cin >> val;
            p = findItem(head, val);
            if (p == NULL)
                cout << "Элемент '%i' не найден\n" << val;
            else {
                cout << "Вставить после узла значение = ";
                cin >> val;
                insertAfterItem(p, val);
                outList(head);
            }
            break;
        case 5:
            cout << "Введите значение удаляемого элемента\n";
            cin >> k;
            p = findPos(head, k);
            if (p == NULL)
                cout << "Элемент не найден\n" << k;
            else
            {
                cout << "Удаляем элемент \n" << p->item;
                head = remove(head, p);

            }

            break;
        case 4:
        {
            int val;
            cout << "Введите значение после которого будет добавлен элемент\n";
            cin >> val;

            cout << "Вставить  узел значение которого= ";
            cin >> val;
            insert(val, head);
            outList(head);
        }
        break;
        case 6:
            head = removeHead(head);
            break;
        case 7:
            if (isEmpty(head)) cout << "Список пуст\n";
            break;
        case 8:
            removeAll(head);
            break;
        case 9:
        {
            cout << "Введите элементы первого списка\nДля завершения введите 0\n";
            cin >> k;
            while (k != 0)
            {
                head = addHead(head, k);
                cin >> k;
            }
            cout << "Введите элементы второго списка\nДля завершения введите 0\n";
            cin >> k;
            while (k != 0)
            {
                tail = addHead(tail, k);
                cin >> k;
            }
            summ = sortlists(head, tail);
            outList(summ);
            break;
        }
        }
    } while (ans != 0);

    return 0;

}