Tortise and Hare Algorithm

detect_cycle.c

#include <assert.h>
#include <stddef.h>
#include <limits.h>
#include <stdio.h>

struct node {
  int value;
  struct node *next;
};

void find_min(struct node *cur) {
    assert(cur != NULL);
    int minval = INT_MAX;
    for (; cur != NULL; cur = cur->next) {
        if (cur->value < minval) {
            minval = cur->value;
        }
    }
    printf("minval=%d\n", minval);
}

int has_cycle(struct node *head) {
    if (head == NULL || head->next == NULL) {
        return 0;
    }
    struct node *tortise, *hare;
    tortise = head;
    hare = head;
    for (int i = 0; hare != NULL; i = i == INT_MAX ? 0 : i + 1) {
        hare = hare->next;
        if (i % 2) {
            tortise = tortise->next;
        }
        if (hare == tortise) {
            return 1;
        }
    }
    return 0;
}

int main() {
    struct node a, b, c, d;

    a.next = &b;
    b.next = &c;
    c.next = &d;
    d.next = &b;
    printf("has cycle = %d\n", has_cycle(&a));
}