Detect Loop in Linked List (Floyd's Cycle Detection)

Floyd's cycle-finding uses two pointers: slow advances one node per step, fast advances two. If there is a cycle, they eventually point to the same node; if fast reaches NULL, the list is acyclic. This needs O(n) time and O(1) extra space (no hash table).

C program (has_cycle returns 1 or 0)

The list is built with insert_begin like insert at beginning (values 50 … 10 so the front is 10 20 30 40 50). We print the list once (acyclic), call has_cycle, then link the tail to the node holding 30 to create a loop, test again, break the loop (tail->next = NULL), and free_list. Never call free_list while a cycle exists.

• Loop condition fast != NULL && fast->next != NULL avoids dereferencing past the end on an acyclic list.
• Finding the start of the cycle (after a meeting point) is a follow-up: move one pointer to head and advance both one step at a time until they meet.

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

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

struct Node *insert_begin(struct Node *head, int data)
{
    struct Node *newNode = malloc(sizeof(struct Node));
    if (newNode == NULL)
        return head;

    newNode->data = data;
    newNode->next = head;
    return newNode;
}

struct Node *find_tail(struct Node *head)
{
    if (head == NULL)
        return NULL;
    struct Node *cur = head;
    while (cur->next != NULL)
        cur = cur->next;
    return cur;
}

struct Node *find_node(struct Node *head, int data)
{
    struct Node *cur = head;
    while (cur != NULL) {
        if (cur->data == data)
            return cur;
        cur = cur->next;
    }
    return NULL;
}

int has_cycle(struct Node *head)
{
    struct Node *slow = head;
    struct Node *fast = head;

    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast)
            return 1;
    }
    return 0;
}

void print_list(struct Node *head)
{
    struct Node *cur = head;
    while (cur != NULL) {
        printf("%d ", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

void free_list(struct Node *head)
{
    struct Node *cur = head;
    while (cur != NULL) {
        struct Node *next = cur->next;
        free(cur);
        cur = next;
    }
}

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

    head = insert_begin(head, 50);
    head = insert_begin(head, 40);
    head = insert_begin(head, 30);
    head = insert_begin(head, 20);
    head = insert_begin(head, 10);

    print_list(head);   /* 10 20 30 40 50 */

    printf("%d\n", has_cycle(head));   /* 0 */

    struct Node *tail = find_tail(head);
    struct Node *join = find_node(head, 30);
    tail->next = join;

    printf("%d\n", has_cycle(head));   /* 1 */

    tail->next = NULL;
    free_list(head);
    return 0;
}

Program output

Overall program flow

has_cycle on the acyclic list (first call)

Example addresses: 10 at 0x5000, 20 at 0x4000, 30 at 0x3000, 40 at 0x2000, 50 at 0x1000.

has_cycle after tail → 30 (cycle)

Fast and slow eventually land on the same node inside the loop; the exact meeting point depends on the cycle shape.

Memory layout (acyclic, before linking tail)

Five nodes (newest insert at head)

Visual representation

Acyclic list (before tail->next = join):

head (0x5000)
   │
   ▼
  10 → 20 → 30 → 40 → 50 → NULL

After linking tail 50 to the node 30 (cycle):

        ┌──────────────────────────┐
        │                          │
        ▼                          │
  10 → 20 → 30 → 40 → 50 ──────────┘

Detailed step-by-step: first iteration of has_cycle (acyclic)

When the list has no cycle, fast reaches the end first. First loop iteration (both start at head):

Complexity summary

The key takeaway is that Floyd's algorithm detects a cycle without extra memory: if the fast pointer laps the slow pointer inside a loop, they meet; if the list ends, there is no cycle.

Alternative: store visited pointers in a hash set—O(n) time and O(n) space. Recursive detection is possible but not needed here.