You are given a pointer to the head of a SINGLY linked list. Write a function that takes as an argument one pointer, and determines whether or not the list is "looped".
A "looped" list means that the linked list has a node that points to a PREVIOUS member (thereby creating a cycle).
Clearly, if a list is looped, and you attempt to simply go from node to each next node until you reach the end, you will never get to an end (just going around and around the loop forever).
Conditions: The list (and the loop, if it exists) may be of any given size (up to available memory), and your function has only 64 bytes (16 4-byte pointers) of available heap/stack space).
***Extra Credit: What is the speed (big-O notation) of your solution?
__________________________________
For those of you non-computer types: a singly linked list is simply a list of records where each record (node) points to the NEXT record. (The only way to get to a node is to first be at the previous node.) The first node is special in that we keep track of where it is.
So, we can always get to the first node, but to get to the second we must first get to the first node. To get to the third, we must first get to the second, and so on.
Therefore, it is an easy matter of traversing all the nodes in order. But it is impossible to go backwards (unless one keeps track of all previously visited nodes) or to access the nodes in any other order (like random access or alphabetically).
Normally, the last node points to NULL, and we generally know to stop at that point.
This problem arises when one of the nodes MIGHT point to a node that occurred in the list previously. (For instance, the 651st node points to the 83rd node.) Then we will end up going from the 651st -> 83rd -> 84th... and continue looping.
The question is... how do we know that we've looped? (And how quickly can we determine whether or not we looped.)
(In reply to
re(3): Racing around by Federico Kereki)
Fredrico,
No flame intended, but I figured it was worth looking at. Complete detailed analysis is a bit messy, due to the 2^N cutoffs, and the answers depend on the relative length of the list and the length of the looped part, if any. So I ran a simulation. Taking lists of random length up to 10000, and looping them back to a random point, I counted the number of times through the inner loop of e.g.'s code and Charlie's code (which I'm biased toward, since it is the same solution I had).
The "inner loop" in Charlie's case does one memory fetch, and some comparisons In e.g.'s case it does 3 memory fetches and some comparisons. In the real world, the number of memory fetches is going to be the deciding factor. I ran 10000 trials, and took the average ratio of the number of times through the inner loop, and the average ratio of the number of memory fetches. In both cases I used e.g.'s value / Charlie's value:
loops: 1.973699
fetches: 0.657914
So in real applications, Charlie's code would run in about 2/3 the time of e.g.'s. This is about what I expected, since Charlie will generally check most items once, and e.g. will check most of them twice.
Here is the test code I used: (I used my implementation of what I've been calling "Charlie's code", and found a bug in my earlier posted code while doing this!):
(Special thanks to SK, who told me about the non-breaking space trick!)
#include <stdio.h>
#include <stdlib.h>
#define MAXLEN 100000
#define END -1
#define ROUNDS 10000
main()
{
int list[MAXLEN];
int N,M,i,j;
int eg_loops,eg_fetch;
int charlie_loops,charlie_fetch;
float rloop,rfetch;
for(i=0; i
list[i]=i+1;
rloop = rfetch = 0;
for(i=0; i
N=rand() % MAXLEN;
if(N==0) N=10;
M=rand() % N;
list[N]=M;
charlie(list,&charlie_loops,&charlie_fetch);
eg(list,&eg_loops,&eg_fetch);
rloop += (float)charlie_loops/(float)eg_loops; rfetch += (float)charlie_fetch/(float)eg_fetch;
list[N]=N+1;
}
rloop /= ROUNDS;
rfetch /= ROUNDS;
printf("Ratios: loop=%f fetch=%f\n",rloop,rfetch);
}
charlie(int *list, int *lc, int *fc)
{
int save, item,count,i;
save=0;
item=list[0];
*lc=0;
*fc=1;
count=1;
while(1) {
for(i=0; i
(*lc)++;
item=list[item];
(*fc)++;
if(item==save) return;
if(item==END) return;
}
count=2*count;
save=item;
}
}
eg(int *list, int *lc, int *fc)
{
int p,q;
p=0;
q=list[0];
*lc=0;
*fc=1;
do {
(*lc)++;
p=list[p];
(*fc)++;
q=list[q];
(*fc)++;
if(q==END) return;
q=list[q];
(*fc)++;
if(q==END) return;
} while(p != q);
return;
}
re(4): Racing around -- simulation
