2
\$\begingroup\$

I have written this code Floyd Cycle finding algorithm. The methods I have used are createLoop() , doesLoopExist(), lengthOfLoop() and insert(). I want to optimise this code and improve using advanced C++.

#include <iostream>

template <class T>
class LinkedList
{
  struct Node
  {
    T data;
    Node * next;
    Node(T value) : data(value), next(nullptr) {}
  };
  Node *head;

public:
  LinkedList() : head(nullptr) {}
  ~LinkedList();
  void insert(T);
  void createLoop(int);
  bool doesLoopExist();
  int lengthOfLoop();
};

template <class T>
void LinkedList<T>::insert(T data)
{
  Node *node = new Node(data);
  Node *tmp = head;
  if(tmp == nullptr)
  {
    head = node;
  }
  else
  {
    while(tmp->next != nullptr)
    {
      tmp = tmp->next;
    }
    tmp->next = node;
  }
}

template <class T>
void LinkedList<T>::createLoop(int n)
{
  Node *tmp = head;
  Node *tail = head;
  for(int i = 0; i < n-1; i++)
  {
    tmp = tmp->next;
  }

  while(tail->next != nullptr)
  {
    tail = tail->next;
  }
  tail->next = tmp;
}

template <class T>
bool LinkedList<T>::doesLoopExist()
{
  Node *slowPtr = head;
  Node *fastPtr = head;

  while(slowPtr && fastPtr && fastPtr->next)
  {
    slowPtr = slowPtr->next;
    fastPtr = fastPtr->next->next;

    if(slowPtr == fastPtr)
    {
      return true;
    }
  }
  return false;
}

template <class T>
int LinkedList<T>::lengthOfLoop()
{
  int count = 0, loopExist = 0;
  Node *slowPtr = head;
  Node *fastPtr = head;
  while(slowPtr && fastPtr && fastPtr->next)
  {
    slowPtr = slowPtr->next;
    fastPtr = fastPtr->next->next;

    if(slowPtr == fastPtr)
    {
      loopExist = 1;
      break;
    }
  }
  if(loopExist)
  {
    fastPtr = fastPtr->next;
    count++;
    while(slowPtr != fastPtr)
    {
      fastPtr = fastPtr->next;
      count++;
    }
    return count;
  }
  return 0;
}

template <class T>
LinkedList<T>::~LinkedList()
{
  Node *tmp = nullptr;
  while(head)
  {
    tmp = head;
    head = head->next;
    delete tmp;
  }
  head = nullptr;
}

int main()
{
  LinkedList<char> ll1;
  ll1.insert('p');
  ll1.insert('r');
  ll1.insert('o');
  ll1.insert('g');
  ll1.insert('r');
  ll1.insert('a');
  ll1.insert('m');
  ll1.insert('m');
  ll1.insert('e');
  ll1.insert('r');

  int nodeNumber = 5;
  //Node number starts from 1

  ll1.createLoop(nodeNumber);
  bool result = ll1.doesLoopExist();
  if(result == true)
  {
    std::cout <<"Loop exist in the Linked List\n";
  }
  else
  {
    std::cout <<"Loop does not exist in the Linked List\n";
  }

  int len = ll1.lengthOfLoop();
  std::cout << "Length of Loop is " << len <<"\n";

  return 0;
}
\$\endgroup\$

1 Answer 1

2
\$\begingroup\$
  • DRY. The first loop of lengthOfLoop is literally identical to doesLoopExist. Replace it with

        loopExist = doesLoopExist();
    

    This also hints that doesLoopExist should be Node * doesLoopExist(), and return a node on the loop or nullptr.

  • The destructor invokes UB when applied to the list with a loop. At the end of the loop the next pointer points to an already deleted node.

  • insert should be better called append.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.