#include <stdio.h>
#include <stdlib.h>

typedef struct Node
{
  struct Node* next;
  int data;
} Node;

// FIND OUT IF THE LINKED LIST HAS A CYCLE
Node* has_cycle(Node* head)
{
  Node *iter,*iter2;
  iter = iter2 = head;

  while (iter && iter2)
  {
    // advance once
    iter = iter->next;

    // advance twice
    iter2 = iter2->next;
    if (!iter2)
      return 0;
    iter2 = iter2->next;

    if (iter == iter2)
      return iter;
  }
  return 0;
}

// print the list and print the cycle more than once for display purpose
void print_circular_list(Node* head, Node* cycle_point)
{
  int cycle_passed = 0;
  Node* iter = head;

  while(iter)
  {
    fprintf(stdout, "%d ", iter->data);
    iter = iter->next;
    if ((iter == cycle_point) && (++cycle_passed >= 3))
      break;
  }
  fprintf(stdout, "...\n");
}

void print(Node* head)
{
  Node *iter;

  iter = head;
  while(iter)
  {
    fprintf(stdout, "%d ", iter->data);
    iter = iter->next;
  }
  fprintf(stdout, "\n");
}

// insert a new value after the given node
// return the new node that was added
Node* insert_after(Node* after, int val, Node* cycle)
{
  Node* next = malloc(sizeof(Node));

  if (next) 
  {
    next->next = cycle;  
    next->data = val;
  }

  if (after)
  {
    after->next = next;  
  }

  return next;
}

int main(int argc, char** argv)
{
  Node *head1 = 0;
  Node *head2 = 0;
  Node *head3 = 0;
  Node *head4 = 0;
  Node *iter, *cycle;

  head1 = iter = insert_after(head1, 1, 0);
  iter = insert_after(iter, 2, 0);
  iter = insert_after(iter, 3, 0);
  iter = insert_after(iter, 4, 0);
  iter = insert_after(iter, 5, 0);
  cycle = has_cycle(head1);
  fprintf(stdout, "has_cycle %d\n", cycle ? 1 : 0);
  print(head1);

  head2 = iter = insert_after(head2, 2, 0);
  iter = insert_after(iter, 4, 0);
  iter = insert_after(iter, 6, 0);
  iter = insert_after(iter, 8, 0);
  iter = insert_after(iter, 10, 0);
  cycle = has_cycle(head2);
  fprintf(stdout, "has_cycle %d\n", cycle ? 1 : 0);
  print(head2);

  head3 = iter = insert_after(head3, 3, 0);
  iter = insert_after(iter, 6, 0);
  iter = insert_after(iter, 9, 0);
  iter = insert_after(iter, 12, 0);
  cycle = iter;
  iter = insert_after(iter, 15, 0);
  iter = insert_after(iter, 18, 0);
  iter = insert_after(iter, 21, 0);
  iter = insert_after(iter, 24, cycle);
  cycle = has_cycle(head3);
  fprintf(stdout, "has_cycle %d\n", cycle ? 1 : 0);
  print_circular_list(head3, cycle);

  return 0;
}