This example in C++ demonstrates two techniques to detect a loop in a linked list. This example determines if a linked list has a cycle. Note that the cycle can occur anywhere - not just the tail node linking back to the head. For example, if the list bec

main.cpp

#include <iostream>
#include <map>
#include <cassert>
#include <climits>
 
namespace std {   };
using namespace std;
 
struct node
{
   node* next;
};
 
struct bin_node
{
   bin_node* left, * right;
   size_t value;
};
 
node* build_linked_list(size_t n)
{
   node* head = NULL;
 
   if (n > 0)
   {
      head = new node;
      head->next = NULL;
 
      node* p = head;
 
      for (size_t i = 1; i < n; ++i)
      {
         p->next = new node;
         p->next->next = NULL;
         p = p->next;
      }
   }
 
   return head;
}
 
node* corrupt_linked_list_tail(node* head, size_t n)
{
   if (head != NULL && n > 0)
   {
      n >>= 1;
      size_t r = rand() % n;
 
      node* p = head;
 
      for (size_t i = 0; i < r; p = p->next, ++i);
 
      node* tail = head;
 
      for (; tail->next != NULL; tail = tail->next);
 
      tail->next = p;
   }
 
   return head;
}
 
bool detect_loop_using_hash_map(node* head)
{
   bool result = false;
 
   map<const node*, bool> detect;
 
   while (head != NULL)
   {
      if (detect[head] != false)
      {
         result = true;
         break;
      }
 
      detect[head] = true;
      head = head->next;
   }
 
   return result;
}
 
bool detect_loop_using_tortoise_and_hare_algorithm(node* head)
{
   node* tortoise = head;
   node* hare = head;
 
   do
   {
      if (hare != NULL)
      {
         hare = hare->next;
 
         if (hare != NULL)
         {
            hare = hare->next;
         }
 
         tortoise = tortoise->next;
      }
      else
      {
         break;
      }
   }
   while (tortoise != hare);
 
   return head != NULL && tortoise == hare;
}
 
bool validate_bin_tree(const bin_node* head = NULL, const size_t my_min = 0, const size_t my_max = 0)
{
   bool result = true;
 
   if (head != NULL)
   {   
      result = head->value > my_min && head->value < my_max && 
               validate_bin_tree(head->left, my_min, head->value) && validate_bin_tree(head->right, head->value, my_max);
   }
 
   return result;
}
 
void flip_bin_tree(bin_node* head = NULL)
{
   if (head != NULL)
   {
      flip_bin_tree(head->left);
      flip_bin_tree(head->right);

      bin_node* p = head->left;
      head->left = head->right;
      head->right = p;
   }

   return;
}

/* This function shall "rotate" a binary tree "90 degrees" clockwise.
   Alas, the result shall not be a valid search binary tree. */
bin_node* invert_bin_tree(bin_node* head = NULL)
{
   bin_node* p = NULL;

   if (head != NULL)
   {
      if (head->left == NULL && head->right == NULL) 
      {
         p = head;
      }
      else
      {
         p = invert_bin_tree(head->left);
    
         head->left->left = head->right;
         head->left->right = head;
         head->left = NULL;
         head->right = NULL;
      }
   }

   return p;
}

int main(int argc, char* argv[])
{
   node* head = build_linked_list(1000);
 
   srand(67);
   corrupt_linked_list_tail(head, 1000);
 
   assert(detect_loop_using_hash_map(head) != false);
   assert(detect_loop_using_tortoise_and_hare_algorithm(head) != false);
 
// Invalid tree:
//       37
//    21    56
// 40
 
   bin_node bin_tree[4];
   bin_tree[0].value = 37;
   bin_tree[0].left  = &bin_tree[1];
   bin_tree[0].right = &bin_tree[2];
   bin_tree[1].value = 21;
   bin_tree[1].left  = &bin_tree[3];
   bin_tree[1].right = NULL;
   bin_tree[2].value = 56;
   bin_tree[2].left  = NULL;
   bin_tree[2].right = NULL;
   bin_tree[3].value = 40;
   bin_tree[3].left  = NULL;
   bin_tree[3].right = NULL;
 
   assert(validate_bin_tree(bin_tree, 0, SIZE_MAX) == false);
 
// Valid tree:
//       37
//    21    56
// 16
 
   bin_tree[3].value = 16;
 
   assert(validate_bin_tree(bin_tree, 0, SIZE_MAX) != false);

   flip_bin_tree(bin_tree);
   
   assert(bin_tree[0].value == 37);
   assert(bin_tree[0].left->value == 56);
   assert(bin_tree[0].right->value == 21);

   return 0;
}