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)
CodePudding user response：
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.
CodePudding user response：
There are some problems with your code:
1) empty list should be nullptr
In main:
linked* head = new linked(1);
should be
linked* head = nullptr;
You start with an empty list. You do not know what data you will insert first and you assume the first value inserted will be 1. With this change you also have to change your insert:
if (p == 1) {
has to check
if (head == nullptr) {
2) replace head with tail
In a circular single linked list you always need the previous node to delete a node or to insert at the head. That means you have to traverse the whole list when given the head to find the previous. This is rather slow, so store the tail of the list instead. Then the head is tail->next and you can delete the head or insert at the head directly.
3) del breaks head
static void del(linked*head, int size) {
If this deletes the first node in the list then the head the caller passed in becomes a dangling pointer. There is no way to update the pointer the caller holds for the list. Just like with insert you need to pass in a reference:
static void del(linked*&head, int size) {
Now for your problem of how to delete the node without extra memory:
You can't. You always need extra memory to temporarily store the node to be deleted while you fix up the links in the list and then delete it. You already needed that extra memory to find the tail of the list and you called it temp.
static void del(linked*&tail) {
if (tail == nullptr) return; // no list, nothing to delete
for (std::size_t skip = 0; tail->next != tail; skip) { // keep going till only one node is left
for(std::size_t i = 0; i < skip; i) tail = tail->next; // skip nodes
// delete node
linked* temp = tail->next;
tail->next = tail->next->next;
delete temp;
}
}