Question

Please debug the code and answer the questions:

#include <stdio.h>
typedef struct node {
int value;
struct node *next;
} node;
int ll_has_cycle(node *first) {
node * head = first;
while (head->next) {
head = head->next;
if (head == first)
return 1;
}
return 0;
}

void test_ll_has_cycle(void) {
int i,j;
node nodes[5];
for(i=0; i < sizeof(nodes)/sizeof(node); i++) {
nodes[i].next = NULL;
nodes[i].value = i;
}

nodes[0].next = &nodes[1];
nodes[1].next = &nodes[2];
nodes[2].next = &nodes[1];
printf("Checking first list for cycles. There should be a cycle,
ll_has_cycle says it has %s cycle\n",
ll_has_cycle(&nodes[1])?"a":"no");
printf("Checking length-zero list for cycles. There should be
none, ll_has_cycle says it has %s cycle\n",
ll_has_cycle(NULL)?"a":"no");
printf("A node value is: %d", nodes[2].value);
}

int main(void) {
test_ll_has_cycle();
return 0;
}

(a) What is the output of this program?

(b) Is there a bug / fault you see from the output console? If so, explain why, fix the bug, and describe how you fixed the bug?

Answer 1

Note: If you like my efforts then please do upvote this answer.

--------------------------------------------------------------------------------------------------

Initially when you run this code it will show the segmentation fault.

So, I am answering the part (b) first.

(b) Yes, there is a bug/fault. The reason of the fault is that there is no null check in the code for cycle detection..We can fix the code by adding these two lines in the code. See the highlighted bold lines in the code.

#include <stdio.h>
typedef struct node {
int value;
struct node *next;
} node;
int ll_has_cycle(node *first) {
if(first == NULL) //Newly added line
return 0; //Newly added line
node * head = first;
while (head->next) {
head = head->next;
if (head == first)
return 1;
}
return 0;
}

void test_ll_has_cycle(void) {
int i,j;
node nodes[5];
for(i=0; i < sizeof(nodes)/sizeof(node); i++) {
nodes[i].next = NULL;
nodes[i].value = i;
}

nodes[0].next = &nodes[1];
nodes[1].next = &nodes[2];
nodes[2].next = &nodes[1];
printf("Checking first list for cycles. There should be a cycle, ll_has_cycle says it has %s cycle\n",ll_has_cycle(&nodes[1])?"a":"no");
printf("Checking length-zero list for cycles. There should be none, ll_has_cycle says it has %s cycle\n", ll_has_cycle(NULL)?"a":"no");
printf("A node value is: %d", nodes[2].value);
}

int main(void) {
test_ll_has_cycle();
return 0;
}

---------------------------------------------------------------------------------------------------

(a) After correcting the fault the output of the code will be: