Last active
August 3, 2018 03:16
-
-
Save quad/1adbf401b9f9488211fd5c21691230e8 to your computer and use it in GitHub Desktop.
Find a cycle in a linked list, for all your tech interview problem needs.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* 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; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# 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) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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