Question

C++ Remove every other node in a circular linked list USING RECURSION. You can only use the preprocessor directives <iostream> and using namespace std;

You must use this prototype:

int remove_every_other(node *&rear)

Answer 1

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

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

struct node *addToEmpty(struct node *last, int data)
{
        // This function is only for empty list
        if (last != NULL)
                return last;

        // Creating a node dynamically.
        struct node *temp = (struct node*)malloc(sizeof(struct node));

        // Assigning the data.
        temp -> data = data;
        last = temp;

        // Creating the link.
        last -> next = last;

        return last;
}


struct node *addEnd(struct node *last, int data)
{
        if (last == NULL)
                return addToEmpty(last, data);

        struct node *temp =
            (struct node *)malloc(sizeof(struct node));

        temp -> data = data;
        temp -> next = last -> next;
        last -> next = temp;
        last = temp;

        return last;
}



void traverse(struct node *last)
{
        struct node *p;

        // If list is empty, return.
        if (last == NULL)
        {
                cout << "List is empty." << endl;
                return;
        }

        // Pointing to first node of the list.
        p = last -> next;

        // Traversing the list.
        do
        {
                cout << p -> data << " ";
                p = p -> next;

        }
        while (p != last->next);

}
struct node *last = NULL;
//  Removing every other node
int remove_every_other(node *&rear) {
        if (rear == NULL)
                return -1;

        if(rear->next == last || rear == last)
                return 0;

        rear->next = rear->next->next;

        remove_every_other(rear->next);

}
// Driven Program
int main()
{

        last = addToEmpty(last, 1);
        last = addEnd(last, 2);
        last = addEnd(last, 3);
        last = addEnd(last, 4);
        last = addEnd(last, 5);
        last = addEnd(last, 6);
        last = addEnd(last, 7);
        last = addEnd(last, 8);
        last = addEnd(last, 9);
        last = addEnd(last, 10);
        last = addEnd(last, 11);

        cout<<"Before removing every other node:\n";
        traverse(last);
        cout << endl;

        remove_every_other(last->next);

        cout<<"After removing every other node:\n";
        traverse(last);
        cout << endl;

        return 0;
}

OUTPUT: