Following is the C implementation of the FCD algorithm following a self-written proof.
C implementation
The following program takes a linked list as input and finds the index of the linked list from where the loop starts.
#include <stdio.h>
#include <stdlib.h>
struct linked_list{
int i;
int* p;
}typedef llis;
int fcda(llis*);
int main(void) {
int n;
scanf("%d",&n);
llis *l;
l = (llis*)malloc(n*sizeof(llis));
for(int i=0; i<n; i++){
scanf("%d", &((l+i)->i));
int k;
scanf("%d", &k);
(l+i)->p = (int*)(l+k);
}
int j;
j=fcda(l);
printf("There is a loop starting from index %d in the linked list and it is calculated using FCD algorithm", j);
return 0;
}
int fcda(llis *l){
llis *p1, *p2, *p3;
p1 = p2 = p3 = l;
do{
p1 = (llis*)p1->p;
p2 = (llis*)p2->p;
p2 = (llis*)p2->p;
}while(p1!=p2);
do{
p3 = (llis*)p3->p;
p2 = (llis*)p2->p;
}while(p3!=p2);
return p3-l;
}
The following is my logic behind the proof of this algorithm.
A question to all the readers, as it came to my mind as I was misinterpreting linked lists while being first introduced to this problem (and which can be seen scribbled at the side in a diagram in the second page):
Consider a linked list with a terminating loop structure where the pointer flips when we access its memory (flips in the sense it now points to the previous element in the linked list), for all except the 0 indexed element. Describe the motion of an external pointer going through the linked list at 1 pace. Also, is the structure different from a closed loop on its own?
Top comments (0)