Hi, I am working on some practice problems for my class and I keep getting stuck on this problem. It is using linked list, I am bit stuck. The problem is to write a function int testloop (listnode *head) that checks to see whether the list 'head' contains a loop.

I just need help on how to approach the problem

``````#include <iostream>

using namespace std;

class listnode {
public:
listnode *next;
};

listnode *l[4];

void create_list();

int main()
{

int i;

cout << "creating lists......\n";
create_list(); // creating lists in *l[4]

for (i=0; i<4; i++) {
cout << "testing list " << i << " .....\n";
if (testloop(l[i]) == 1)
cout << "    list " << i << " has a loop.\n";
else
cout << "    list " << i << " does not have a loop.\n\n";
}
}``````

To test if it contains a loop, i.e is a circular linked list, what you need to do is transverse through the list, and see if head comes up twice. Here is some psuedo-code.

``````bool isLoopedLinkedList(const listnode* head){
- bool result = false
- while headCopy-> next is not null
- if so the set result to true and break out of loop
- else continue
- endWhile
}``````

> if it contains a loop, i.e is a circular linked list

Not exactly. The loop not necessarily includes the head (consider 1->2->3->2). In that case your algorithm will run forever.

The solution takes two pointers traversing the list with different "speeds":

``````pointer1 <- head
do:
pointer1 <- next(pointer1)
pointer2 <- next(next(pointer2))
until
- either one of the pointers hits the end of list (not a loop)
- or pointer1 becomes equal to pointer2 (loop detected)``````

> if it contains a loop, i.e is a circular linked list

Not exactly. The loop not necessarily includes the head (consider 1->2->3->2). In that case your algorithm will run forever.

The solution takes two pointers traversing the list with different "speeds":

``````pointer1 <- head