Sunday, December 22, 2013

Find list is circular list or not

class single_link_list
{
struct node
{
int element;
node* link;
}*first_node;
public:
single_link_list()
{
first_node = NULL;
}
void change_list_to_circular();
bool is_list_circular();
};

bool Linked_list::is_list_circular()
{
    bool status = false;
    node* slower_iteration = first_node;
    node* faster_iteration = first_node;
    while(faster_iteration  && slower_iteration)
    {
        if(faster_iteration->next_node == slower_iteration )
            {
                   status = true;
                  return status;
            }
       
        else if(faster_iteration == NULL || faster_iteration->next_node == NULL)
            {
              return status;
             }
        else
        {
         faster_iteration= faster_iteration->next_node->next_node;
         slower_iteration = slower_iteration->next_node;
        }
    }
    return status;
}

void single_link_list::change_list_to_circular()
{
//for changing list to circular last node shall point to first node
node* temp_node = first_node;
while(temp_node->link != NULL)
{
temp_node = temp_node->link;
}
temp_node->link = first_node;
}


int main()
{
single_link_list *ptr =  new single_link_list();
int element = 10;
ptr->insert_in_list(element); // for insert refer old post in same blog
ptr->insert_in_list(element + 5 ); // for insert refer old post in same blog
ptr->insert_in_list(element + 10); // for insert refer old post in same blog
ptr->insert_in_list(element + 15); // for insert refer old post in same blog
        bool is_circular = ptr->is_list_circular();
ptr->change_list_to_circular();
printf(" \n After calling  change_list_to_circular(): \n");
is_circular = ptr->is_list_circular();

return 0;
}

Output would be:




No comments: