Floyd's tortoise and hare algorithm for cycle detection.

floyd_tah.c

// Created by Derick Alangi on 6/28/21.

/* Simple cycle detection algorithm */

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

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

Node* find_cycle(Node* c_list);

Node* find_cycle(Node* c_list) {
    Node* p1, *p2;

    if (c_list == NULL)
        return NULL;
    p1 = c_list;
    p2 = c_list;
    while (p2->next != NULL && p2->next->next != NULL)
    {
        p1 = p1->next;
        p2 = p2->next->next;
        if (p1 == p2)
        {
            p1 = c_list;
            while (p1 != p2)
            {
                p1 = p1->next;
                p2 = p2->next;
            }
            return p2;
        }
    }
    return NULL;
}

int main(void) {
    Node* head = NULL, *temp = NULL;

    int i;
    head = (Node*)malloc(sizeof(Node*));

    if (head == NULL)
        printf("Memory could not be allocated!\n");

    head->data = 0;
    head->next = NULL;
    Node* track = head;

    for (i = 1; i <= 10; i++) {
        temp = (Node*)malloc(sizeof(Node*));
        temp->data = i;
        head->next = temp;
        head = head->next;
        head->next = NULL;
    }
    // Create a cycle here: list tail points back to head
    head->next = track;

    // Test Floyd Tortoise and Hare algorithm
    Node* ftah = find_cycle(track);

    printf("A cycle was detected at node: %d.\n", ftah->data);

    return 0;
}