Detect loop in linked list (Floyd cycle finding algorithm)

Question

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;
}

Answer 1

• 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.