I've come across a problem in dynamic programming in which we are asked to delete nodes of a circular LinkedList, in the following manner. Delete the first node then skip one and delete the next, then skip two and delete the next, then skip three and delete the next and it continues until we are left with only one node, and that one node is our answer. For example, if we have 5 nodes, then the nodes will be deleted in the following order – 1 3 2 5 4, and the last node would be 4. Similarly, if we have 4 nodes, then the nodes will be deleted in the following order – 1 3 4 2, and the last node would be 2.
This is a screenshot of the part of the code that requires improvement
using this code in c++, I've been successful in solving the problem but I want to free the memory using delete command as I delink a node. Can anyone please help me to solve this problem by improving this code (while using minimal memory)?
The node can be deleted by declaring another pointer, but that would only increase the memory usage, which I don't want at the moment.
The entire code is given below
#include<iostream>
using namespace std;
class linked {
public:
int x;
linked* next;
//methods
linked(int p); //constructor
static void insert(linked*& head, int p);//method to insert new node
static int print(linked* head);//method to print the result
static void del(linked*head, int size) {//method to delete all the undesired nodes
linked* temp = head;
while (temp->next != head) {//traversing until we find the node just behind the node we want to del
temp = temp->next;
}
for(int i=1;i < size;i++) {
for (int k = 1; k < i; k++) {//del nodes with increment
temp = temp->next;
}
temp->next = temp->next->next; //delinking the
}
}
};
int main() {
int no_of_nodes;
cout << "enter the number of nodes you want to have" << endl;
cin >> no_of_nodes;
linked* head = new linked(1);
for (int i = 1; i <= no_of_nodes; i++) {
linked::insert(head, i);//for inserting nodes, as desired by the user
}
linked::del(head, no_of_nodes);
cout<< linked::print(head);
}
linked::linked(int p) {
x = p;
next = NULL;
}
void linked::insert(linked*& head, int p) {
linked* temp = head;
linked* n = new linked(p);//for the new node
if (p == 1) {
head->next = head;
return;
}
while (temp->next != head) {
temp = temp->next;
}
temp->next = n;
n->next = head;
}
int linked::print(linked* head) {
linked* temp = head;
for (int i = 0; i < 25; i++) {//this can go longer(or shorter), i limited it to 25 only, just to ensure that it is a circular linked list
temp = temp->next;
if (temp == temp->next) {
return temp->x;
}
}
cout << endl;
}
P.S. The problem was taken from ICPC Asia Topi 2022, link: (https://giki.edu.pk/wp-content/uploads/2022/03/ICPC_Day_2.pdf)
It seems neither professional programmer are going to help you.:)
So we, beginners, should help each other.:)
You should declare a class of the circular singly-linked list with non-static member functions.
As for the task to remove all elements from the circular singly-linked list except one using the described algorithm then I can suggest the following approach.
At first within the function remove the cycling. This will make easy to remove elements from the circular singly-linked list. After all elements except one will be removed then restore the cycling.
Here is a demonstration program.
#include <iostream>
#include <utility>
#include <stdexcept>
class CircularList
{
private:
struct Node
{
int data;
Node *next;
} *head = nullptr;
public:
CircularList() = default;
CircularList( const CircularList & ) = delete;
CircularList &operator =( const CircularList & ) = delete;
~CircularList()
{
clear();
}
void clear()
{
if (head)
{
Node *current = head;
do
{
delete std::exchange( current, current->next );
} while (current != head);
head = nullptr;
}
}
void insert( int data )
{
Node *new_node = new Node{ data };
if (not head)
{
new_node->next = new_node;
head = new_node;
}
else
{
Node *current = head;
while (current->next != head) current = current->next;
new_node->next = head;
current->next = new_node;
}
}
const int & top() const
{
if (not head)
{
throw std::out_of_range( "Error. The list is empty." );
}
return head->data;
}
void remove_except_one()
{
if (head)
{
Node *last = head;
while (last->next != head) last = last->next;
last->next = nullptr;
Node **current = &head;
for (size_t n = 0; head->next != nullptr; ++n)
{
for (size_t i = 0; i != n; i++)
{
current = &( *current )->next;
if (*current == NULL) current = &head;
}
Node *tmp = *current;
// The statement below is uncommented for the debug pyrpose.
std::cout << ( *current )->data << '\n';
*current = ( *current )->next;
if (*current == nullptr) current = &head;
delete tmp;
}
head->next = head;
}
}
friend std::ostream &operator <<( std::ostream &os, const CircularList &list )
{
if (list.head)
{
const Node *current = list.head;
do
{
os << current->data << " -> ";
current = current->next;
} while (current != list.head);
}
return os << "null";
}
};
int main()
{
CircularList list;
for (int i = 0; i < 5; i++)
{
list.insert( i + 1 );
}
std::cout << "The list: ";
std::cout << list << '\n';
list.remove_except_one();
std::cout << "The list: ";
std::cout << list << '\n';
list.clear();
std::cout << '\n';
for (int i = 0; i < 4; i++)
{
list.insert( i + 1 );
}
std::cout << "The list: ";
std::cout << list << '\n';
list.remove_except_one();
std::cout << "The list: ";
std::cout << list << '\n';
}
The program output is
The list: 1 -> 2 -> 3 -> 4 -> 5 -> null
1
3
2
5
The list: 4 -> null
The list: 1 -> 2 -> 3 -> 4 -> null
1
3
4
The list: 2 -> null
Within the function remove_except_one this statement
std::cout << ( *current )->data << '\n';
is present for the debug purpose only. You may remove or comment it if you want.