mergeLinkedList.cpp

#include <bits/stdc++.h>
using namespace std;

typedef struct node
{
    int data;
    node *next = NULL;
} node;

void mainMenu()
{
    cout << "\n==================MAIN MENU(Link list 1)==================" << endl;
    cout << "1. Insert At head" << endl;
    cout << "2. Insert before value" << endl;
    cout << "3. Insert after value" << endl;
    cout << "4. Insert at tail" << endl;
    cout << "5. Delete At head" << endl;
    cout << "6. Delete before value" << endl;
    cout << "7. Delete after value" << endl;
    cout << "8. Delete at tail" << endl;
    cout << "9. Traverse the link list" << endl;
    cout << "10. Count the element" << endl;
    cout << "11. Reverse the link List" << endl;
    cout << "\n==================MAIN MENU(Link list 2)==================" << endl;
    cout << "12. Insert At head" << endl;
    cout << "13. Insert before value" << endl;
    cout << "14. Insert after value" << endl;
    cout << "15. Insert at tail" << endl;
    cout << "16. Delete At head" << endl;
    cout << "17. Delete before value" << endl;
    cout << "18. Delete after value" << endl;
    cout << "19. Delete at tail" << endl;
    cout << "20. Traverse the link list" << endl;
    cout << "21. Count the element" << endl;
    cout << "22. Reverse the link List" << endl;
    cout << "23. Merge the sorted link List" << endl;
    cout << "24. Print merged linkedlist" << endl;
    cout << "25. Exit" << endl;
}
int countNodeNumber(node *head)
{
    int count = 0;
    node *temp = head;
    while (temp != NULL)
    {
        temp = temp->next;
        count++;
    }
    return count;
}
void traverseLL(node *head)
{
    node *temp = head;

    if (temp == NULL)
    {
        cout << "Empty linked list";
        return;
    }
    cout << endl;
    while (temp != NULL)
    {
        cout << temp->data << " -> ";
        temp = temp->next;
    }
    cout << "NULL";
}

node *insertAtHead(node *head, int val)
{
    node *ptr = new node();
    ptr->data = val;
    ptr->next = head;
    head = ptr;
    return head;
}
node *insertBefore(node *head, int key, int val)
{
    if (head == NULL)
    {
        cout << "Linked list is empty so key doesn't exist";
        return head;
    }
    node *temp = head;
    node *nodePtr = new node();
    nodePtr->data = val;
    if (head->data == key)
    {
        head = insertAtHead(head, val);
        return head;
    }
    while (temp->next != NULL && temp->next->data != key)
        temp = temp->next;
    if (temp->next == NULL && temp->data != key)
    {
        cout << "Key doesn't exist";
        return head;
    }

    nodePtr->next = temp->next;
    temp->next = nodePtr;
    return head;
}
node *insertAfter(node *head, int key, int val)
{
    if (head == NULL)
    {
        cout << "Linked list is empty so key doesn't exist";
        return head;
    }
    node *temp = head;
    node *nodePtr = new node();
    nodePtr->data = val;

    while (temp->data != key && temp->next != NULL)
        temp = temp->next;
    if (temp->data != key && temp->next == NULL)
    {
        cout << "Key doesn't exist";
        return head;
    }
    nodePtr->next = temp->next;
    temp->next = nodePtr;
    return head;

    return head;
}
node *insertAtTail(node *head, int val)
{
    node *ptr = new node();
    if (head == NULL)
    {
        ptr->data = val;
        head = ptr;
    }
    else
    {
        node *temp = head;
        while (temp->next != NULL)
            temp = temp->next;
        ptr->data = val;
        temp->next = ptr;
    }
    return head;
}

node *deleteAtHead(node *head)
{
    if (head->next == NULL)
    {
        delete (head);
        head = NULL;
        return head;
    }
    node *temp = head->next;
    delete (head);
    head = temp;
    return head;
}

node *deleteBefore(node *head, int key)
{
    if (head == NULL)
    {
        cout << "Can't delete as linked list is empty";
        return head;
    }
    if (head->data == key)
        return head;
    if (head->next->data == key)
    {
        head = deleteAtHead(head);
        return head;
    }
    node *currentNodePtr = head->next;
    node *prevNodePtr = head;
    while (currentNodePtr->next != NULL && currentNodePtr->next->data != key)
    {
        prevNodePtr = currentNodePtr;
        currentNodePtr = currentNodePtr->next;
    }
    // if (currentNodePtr->next == NULL )
    if (currentNodePtr->next == NULL && currentNodePtr->data != key)
    {
        cout << "Key doesn't exist";
        return head;
    }
    prevNodePtr->next = currentNodePtr->next;
    delete (currentNodePtr);
    return head;
}

node *deleteAfter(node *head, int key)
{
    if (head == NULL)
    {
        cout << "Can't delete as linked list is empty";
        return head;
    }
    node *temp = head;
    while (temp->next != NULL && temp->data != key)
        temp = temp->next;
    if (temp->next == NULL)
    {
        if (temp->data != key)
            cout << "Key doesn't exist";
        else
            cout << "Key exist as tail so no node is deleted";
        return head;
    }
    node *temp2 = temp;
    temp->next = temp->next->next;
    delete (temp2->next);

    return head;
}

void deleteTail(node *head)
{
    if (head == NULL)
    {
        cout << "Linked List doesn't exists.";
        return;
    }
    if (head->next == NULL)
        head = deleteAtHead(head);
    node *temp = head;
    while (temp->next->next != NULL)
        temp = temp->next;
    delete (temp->next);
    temp->next = NULL;
}

node *reverseLL(node *head)
{
    if (head == NULL)
    {
        cout << "Can't do the reverse as linked list is empty";
        return head;
    }
    if (head->next == NULL)
        return head;
    node *prevNode = NULL;
    node *currentNode = head;
    node *nextNode = NULL;
    while (currentNode != NULL)
    {
        nextNode = currentNode->next;
        currentNode->next = prevNode;
        prevNode = currentNode;
        currentNode = nextNode;
    }
    head = prevNode;
    return head;
}

node *mergeLinklist(node *head1, node *head2)
{
    // node *head = new node();
    node *head = NULL;
    node *temp1 = head1;
    node *temp2 = head2;
    while (temp1 != NULL && temp2 != NULL)
    {
        if (temp1->data < temp2->data)
        {
            head = insertAtTail(head, temp1->data);
            temp1 = temp1->next;
        }
        else
        {
            head = insertAtTail(head, temp2->data);
            temp2 = temp2->next;
        }
    }
    if (temp1 == NULL)
    {
        while (temp2 != NULL)
        {
            head = insertAtTail(head, temp2->data);
            temp2 = temp2->next;
        }
    }
    else
    {
        while (temp1 != NULL)
        {
            head = insertAtTail(head, temp1->data);
            temp1 = temp1->next;
        }
    }

    return head;
}

int main()
{
    int switchCase = 0;
    int in;

    node *head = NULL;
    node *head2 = NULL;
    node *mergedListHead = NULL;
    int startLinkSize1 = 0;
    int startLinkSize2 = 0;

    cout << "Enter the starting linked List 1 size :";
    cin >> startLinkSize1;
    cout << "Enter the starting linked List 2 size :";
    cin >> startLinkSize2;
    cout << "Enter the element with space or enter in between them in sorted manner for list 1 :";
    int temp;
    while (startLinkSize1 != 0)
    {
        cin >> temp;
        head = insertAtTail(head, temp);

        startLinkSize1--;
    }
    cout << "Enter the element with space or enter in between them in sorted manner for list 2 :";

    while (startLinkSize2 != 0)
    {
        cin >> temp;
        head2 = insertAtTail(head2, temp);

        startLinkSize2--;
    }
    while (switchCase != 25)
    {
        mainMenu();
        cin >> switchCase;
        switch (switchCase)
        {
        case 1:
            cout << "Enter the data value" << endl;
            cin >> in;
            cout << endl;
            head = insertAtHead(head, in);
            break;
        case 2:
        {
            int key;
            cout << "Enter the data value before which you want to add new node" << endl;
            cin >> key;
            cout << "Enter the data value" << endl;
            cin >> in;
            cout << endl;
            head = insertBefore(head, key, in);
            break;
        }
        case 3:
        {
            int key;
            cout << "Enter the data value after which you want to add new node" << endl;
            cin >> key;
            cout << "Enter the data value" << endl;
            cin >> in;
            cout << endl;
            head = insertAfter(head, key, in);
            break;
        }
        case 4:
            cout << "Enter the data value" << endl;
            cin >> in;
            cout << endl;
            head = insertAtTail(head, in);
            break;
        case 5:
            head = deleteAtHead(head);
            break;
        case 6:
            cout << "Enter the data value before which node will be deleted" << endl;
            cin >> in;
            cout << endl;
            head = deleteBefore(head, in);
            break;
        case 7:
            cout << "Enter the data value after which node will be deleted" << endl;
            cin >> in;
            cout << endl;
            head = deleteAfter(head, in);
            break;
        case 8:
            deleteTail(head);
            break;
        case 9:
            traverseLL(head);
            break;
        case 10:
            cout << countNodeNumber(head);
            break;
        case 11:
            head = reverseLL(head);
            break;
        case 12:
            cout << "Enter the data value" << endl;
            cin >> in;
            cout << endl;
            head2 = insertAtHead(head2, in);
            break;
        case 13:
        {
            int key;
            cout << "Enter the data value before which you want to add new node" << endl;
            cin >> key;
            cout << "Enter the data value" << endl;
            cin >> in;
            cout << endl;
            head2 = insertBefore(head2, key, in);
            break;
        }
        case 14:
        {
            int key;
            cout << "Enter the data value after which you want to add new node" << endl;
            cin >> key;
            cout << "Enter the data value" << endl;
            cin >> in;
            cout << endl;
            head2 = insertAfter(head2, key, in);
            break;
        }
        case 15:
            cout << "Enter the data value" << endl;
            cin >> in;
            cout << endl;
            head2 = insertAtTail(head2, in);
            break;
        case 16:
            head2 = deleteAtHead(head2);
            break;
        case 17:
            cout << "Enter the data value before which node will be deleted" << endl;
            cin >> in;
            cout << endl;
            head2 = deleteBefore(head2, in);
            break;
        case 18:
            cout << "Enter the data value after which node will be deleted" << endl;
            cin >> in;
            cout << endl;
            head2 = deleteAfter(head2, in);
            break;
        case 19:
            deleteTail(head2);
            break;
        case 20:
            traverseLL(head2);
            break;
        case 21:
            cout << countNodeNumber(head2);
            break;
        case 22:
            head2 = reverseLL(head2);
            break;
        case 23:
            mergedListHead = mergeLinklist(head, head2);
            break;

        case 24:
            cout << "Print merged linkedlist";
            traverseLL(mergedListHead);
            break;
        case 25:
            switchCase = 25;
            break;
        default:
            break;
        }
    }
    return 0;
}