Find a cycle in a linked list, for all your tech interview problem needs.

cycle.c

/* Production C version */

#include <assert.h>
#include <setjmp.h>
#include <signal.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

struct list {
	struct node *head;
	struct node *tail;
};

struct node {
	struct node *next;
};

struct list list_new() {
	return (struct list) { NULL, NULL };
}

void list_append(struct list *list)
{
	if (list->tail) {
		list->tail->next = calloc(1, sizeof(struct node));
		list->tail = list->tail->next;
	} else {
		list->head = list->tail = calloc(1, sizeof(struct node));
	}
}

sigjmp_buf env;

void found_cycle(__attribute__((unused)) int sig) {
	siglongjmp(env, true);
}

bool has_cycle(struct list list) {
	if (sigsetjmp(env, 1)) {
		return true;
	}
	signal(SIGABRT, found_cycle);

	struct node *head = list.head;
	while(head) {
		struct node *next = head->next;
		free(head);
		head = next;
	}

	signal(SIGABRT, SIG_DFL);

	return false;
}

int main(void) {
	struct list empty_list = list_new();

	struct list normal_list = list_new();
	list_append(&normal_list);
	
	struct list cycle_list = list_new();
	list_append(&cycle_list);
	list_append(&cycle_list);
	cycle_list.head->next = cycle_list.head;

	assert(!has_cycle(empty_list));
	assert(!has_cycle(normal_list));
	assert(has_cycle(cycle_list));

	printf("ok\n");

	return 0;
}

cycle.py

# Python prototype version

class Node:
    def __init__(self, next):
        self.next = next

def has_cycle(head):
    while head:
        try:
            next = head.next
        except AttributeError:
            return True

        del head.next
        head = next

    return False

if __name__ == '__main__':
    empty_list = Node(None)
    assert not has_cycle(empty_list)

    normal_list = Node(next=Node(None))
    assert not has_cycle(normal_list)

    cycle_list = Node(Node(None))
    cycle_list.next = Node(cycle_list)
    assert has_cycle(cycle_list)

Makefile

CFLAGS=-Wall -Wextra -Werror -std=c99 -O

all: cycle
	./cycle

cycle: cycle.c