</>EmbeddedInterview

How do you detect a loop in a linked list?

MediumData Structures & Algorithms

Short answer: Use Floyd's tortoise-and-hare algorithm: move one pointer by one node and another by two. If there is a cycle, the fast pointer eventually laps the slow one and they meet; if the fast pointer reaches NULL, there is no cycle. To find where the loop starts, move one pointer back to the head after they meet and advance both one step at a time; they meet at the loop's first node. O(n) time, O(1) memory.

#include <stdbool.h>
#include <stddef.h>
#include <stdio.h>

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

struct node *loop_start(struct node *h)
{
    struct node *slow = h, *fast = h;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {                  /* inside the loop */
            slow = h;
            while (slow != fast) { slow = slow->next; fast = fast->next; }
            return slow;                     /* first node of the loop */
        }
    }
    return NULL;                             /* no loop */
}

int main(void)
{
    struct node n[5];
    for (int i = 0; i < 5; i++) { n[i].val = i; n[i].next = (i < 4) ? &n[i + 1] : &n[2]; }
    struct node *s = loop_start(&n[0]);
    printf("loop starts at %d\n", s ? s->val : -1);   /* 2 */
    n[4].next = NULL;
    printf("loop: %s\n", loop_start(&n[0]) ? "yes" : "no");   /* no */
    return 0;
}

Why the restart works: if the distance from the head to the loop start is a, and they meet b nodes into a loop of length L, the fast pointer travelled twice as far, so a + b is a multiple of L; therefore walking a more steps from the meeting point lands on the loop start, exactly when the other pointer arrives from the head.

Loop length: after they meet, keep one pointer fixed and count steps until the other returns.

Alternatives: a visited set (hash table, O(n) memory), or marking nodes (modifies data). Brent's algorithm is a faster variant.

Embedded relevance: corrupted linked lists (e.g. a free list or a timer list after a memory overwrite) can form cycles that hang the system; a debug check with Floyd's algorithm finds them.