main (1).cpp

/**
 * 
 * Problem Statement-
 * Cycle Detection - [https://www.hackerrank.com/challenges/detect-whether-a-linked-list-contains-a-cycle/problem]
 * 
*/

#include <bits/stdc++.h>

using namespace std;

//class to define a node
class SinglyLinkedListNode
{
public:
  int data;
  SinglyLinkedListNode *next;

    SinglyLinkedListNode (int node_data)
  {
    this->data = node_data;
    this->next = nullptr;
  }
};

//class to define linkedlist
class SinglyLinkedList
{
public:
  SinglyLinkedListNode * head;
  SinglyLinkedListNode *tail;

    SinglyLinkedList ()
  {
    this->head = nullptr;
    this->tail = nullptr;
  }

  //function to insert a node
  void insert_node (int node_data)
  {
    SinglyLinkedListNode *node = new SinglyLinkedListNode (node_data);
    if (!this->head)
      {
	this->head = node;
      }
    else
      {
	this->tail->next = node;
      }
    this->tail = node;
  }
};

//function to print linkedlist
void
print_singly_linked_list (SinglyLinkedListNode * node, string sep,
			  ofstream & fout)
{
  while (node)
    {
      fout << node->data;
      node = node->next;
      if (node)
	{
	  fout << sep;
	}
    }
}

void
free_singly_linked_list (SinglyLinkedListNode * node)
{
  while (node)
    {
      SinglyLinkedListNode *temp = node;
      node = node->next;
      free (temp);
    }
}

//function to detect cycle in linkedlist
bool
has_cycle (SinglyLinkedListNode * head)
{
  SinglyLinkedListNode *cur = head;
  SinglyLinkedListNode *cur1 = head;
  while (cur1 != NULL && cur1->next != NULL)
    {
      cur = cur->next;
      cur1 = cur1->next->next;
      if (cur == cur1)
	return true;
    }
  return false;
}

int
main ()
{
  ofstream fout (getenv ("OUTPUT_PATH"));
  int tests;
  cin >> tests;
  cin.ignore (numeric_limits < streamsize >::max (), '\n');
  for (int tests_itr = 0; tests_itr < tests; tests_itr++)
    {
      int index;
      cin >> index;
      cin.ignore (numeric_limits < streamsize >::max (), '\n');
      SinglyLinkedList *llist = new SinglyLinkedList ();
      int llist_count;
      cin >> llist_count;
      cin.ignore (numeric_limits < streamsize >::max (), '\n');
      for (int i = 0; i < llist_count; i++)
	{
	  int llist_item;
	  cin >> llist_item;
	  cin.ignore (numeric_limits < streamsize >::max (), '\n');
	  llist->insert_node (llist_item);
	}
      SinglyLinkedListNode *extra = new SinglyLinkedListNode (-1);
      SinglyLinkedListNode *temp = llist->head;
      for (int i = 0; i < llist_count; i++)
	{
	  if (i == index)
	    {
	      extra = temp;
	    }
	  if (i != llist_count - 1)
	    {
	      temp = temp->next;
	    }
	}
      temp->next = extra;
      bool result = has_cycle (llist->head);
      fout << result << "\n";
    }
  fout.close ();
  return 0;
}