Skip to content

Instantly share code, notes, and snippets.

@quad quad/Makefile
Last active Aug 3, 2018

Embed
What would you like to do?
Find a cycle in a linked list, for all your tech interview problem needs.
/* 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();
assert(!has_cycle(empty_list));
struct list normal_list = list_new();
list_append(&normal_list);
assert(!has_cycle(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(cycle_list));
printf("ok\n");
return 0;
}
# 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)
CFLAGS=-Wall -Wextra -Werror -std=c99 -O
all: cycle
./cycle
cycle: cycle.c
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.