Singly linked list loop detection.

loop.c

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

struct sList {
   struct sList * next;
   int data;
};

struct sList* sList_new();

struct sList* sList_alloc(struct sList * const next, const int n);

struct sList* sList_tail(struct sList * const list);

struct sList* sList_append(struct sList* list, const int n);

void sList_free(struct sList* list);

int sList_hasLoop(struct sList* list);

int main() {
   struct sList* testList = sList_new();
   struct sList* loopedList = sList_new();

   testList = sList_append(testList, 2);
   testList = sList_append(testList, 5);
   testList = sList_append(testList, 7);

   loopedList = sList_append(loopedList, 3);
   loopedList = sList_append(loopedList, 6);
   loopedList = sList_append(loopedList, 9);

   /* give this list a loop */
   sList_tail(loopedList) -> next = loopedList;

   /* detect loops */
   printf("%i %i\n", 
      sList_hasLoop(testList), 
      sList_hasLoop(loopedList) );

   sList_free(testList); testList = NULL;

   /* note we don't currently free the looped list
    * because iterating over it in the conventional
    * way is impossible */

   /* sList_free(loopedList); //the current version would segfault */

   return 0;
}

struct sList* sList_new() {
   return NULL;
}

struct sList* sList_alloc(struct sList * const next, const int n) {
   struct sList* newList = malloc(sizeof(struct sList));

   assert( newList != NULL);

   newList -> data = n;
   newList -> next = next;

   return newList;
}

struct sList* sList_tail(struct sList * const list) {
   if(list == NULL) { return NULL; }
   else {
      struct sList* listPtr = list;

      while( listPtr -> next != NULL ) {
         listPtr = listPtr -> next;
      }

      return listPtr;
   }
}


struct sList* sList_append( struct sList* list, const int n) {
   struct sList* newTail = sList_alloc(NULL, n);

   if( list == NULL ) {
      /* allocate a node and make it the head */

      return newTail;
   } else {
      /* iterate down the list and make new tail */

      sList_tail( list ) -> next = newTail;

      return list;
   }
}

void sList_free( struct sList* list ) {
   if( list == NULL ) {
      return;
   } else if( list -> next == NULL ) {
      free( list );
   }  else {
      sList_free( list -> next );
      free( list );
   }
}

/* 
* algo adapted from: http://ostermiller.org/find_loop_singly_linked_list.html 
* runs in O(n) without allocating extra memory.
*/
int sList_hasLoop(struct sList* list) {
   struct sList* slowNode = list;
   struct sList* fastNode = list;
   struct sList* fastNode2 = list;

   while((slowNode != NULL) && 
      (fastNode = fastNode2 -> next) &&
      (fastNode2 = fastNode -> next)) {
         if(slowNode == fastNode || slowNode == fastNode2 ) {
            return 1;
         } else {
            slowNode = slowNode -> next;
         }
   }

   return 0;
}