verifying loop in a linked list

[funprogrammer]

I was trying to implement Floyd's cycle finding algorithm to find loops in linked list. I implemented my code using 2 pointers but I am not able to figure out why my output is always is 0 even though a loop exists in the code.
Any suggestions? Can you find my bug?

#include "iostream"
using namespace std;

struct Node{
   int value;
   Node* next;
};

class LinkedList{
   Node* head;
public:
   LinkedList(){
      head = NULL;
   }
   void addNode(int value);
   void wrapAround();
   bool isCyclic();
};

void LinkedList::addNode(int val){
   if (head == NULL){
      head = new Node();
      head->value = val;
      head->next = NULL;
   }
   else{
      Node* temp = head;
	  while(temp->next!=NULL){
         temp = temp->next;
	  }
	  Node* temp2 = new Node();
	  temp2->value = val;
      temp2->next = NULL;
	  temp->next = temp2;
   }
}

void LinkedList::wrapAround(){
   Node* temp = head;
   while(temp->next!=NULL){
      temp = temp->next;
   }
   temp->next = head;
}
bool LinkedList::isCyclic(){
   Node *n1, *n2;
   n1 = head->next;
   n2 = n1->next;
   while(n1!=n2 && n1!=head){
      n1 = n1->next;
      n2=n1->next->next;

     if(n1==n2){
        return true;
     }
   }
   return false;
}
int main(){
   LinkedList L1;
   L1.addNode(5);
   L1.addNode(6);
   L1.addNode(7);
   L1.addNode(3);
   L1.addNode(1);
   L1.wrapAround();
   bool loopTest = L1.isCyclic();
   cout << "loop test is " << loopTest << endl;
   return 0;
}

[funprogrammer]

Can someone look at this and help me out?

[ciphermagi]

Your addNode function is especially and unnecessarily complex.

Basically, if I'm not mistaken, the conditional test for equality is inside the while loop that only allows inequalities to get in. So you will always have a return of false, except in the case that n1->next == n1 evaluates as true. If your loop occurs somewhere else, you'll still get that there is no loop.

That's just on a glance, though, so I may be missing something.

I'm not used to looking at C++ code presently. I know that you could do pretty much exactly what you've done here in C with about 1/4 the lines, maybe less, and that's kind of a big deal. Concise code, as long as it's understandable, will help you debug.

EDIT:
Excuse me. You'll also get a true value on n1->next->next == n1 being evaluated as true. I'm not sure why you put the list advancements there, or why you did them the way you did.

[ciphermagi]

I don't know if this is what you wanted to have happen, but your algorithm isn't sustainable the way it's written. You'll need to make a few modifications if you want to actually prove that the list is cyclical on anything of significant size. Say size of 10. At that point you wouldn't go around far enough to actually run across the first pointer, and so your program wouldn't be able to tell that it does loop back around to head eventually.

You also need to change your addNode function significantly. Look up tail pointers.

#include <iostream>

using namespace std;

struct Node{
	int value;
	Node* next;
};

class LinkedList{
	Node* head;
public:
	LinkedList(){
		head = NULL;
	}
	void addNode(int value);
	void wrapAround();
	bool isCyclic();
};

void LinkedList::addNode(int value)
{
	if (head == NULL){
		head = new Node();
		head->value = value;
		head->next = NULL;
		cout << "Added node to head with value " << value << endl;
	}
	else{
		Node* temp = head;
		while(temp->next != NULL){
			cout << temp->value << endl;
			temp = temp->next;
		}
		Node* temp2 = new Node();
		cout << temp->value << endl;
		temp2->value = value;
		temp2->next = NULL;
		temp->next = temp2;
		cout << "Added node to tail with value " << value << endl;
	}
}

void LinkedList::wrapAround()
{
	Node* temp = head;
	while(temp->next != NULL){
		cout << temp->value << endl;
		temp = temp->next;
	}
	cout << temp->value << endl;
	temp->next = head;
}

bool LinkedList::isCyclic()
{
	Node *n1, *n2;
	n1 = head;
	n2 = head->next;
	cout << n1->value << " " << n2->value << endl;
	do{
		n1 = n1->next;
		n2 = n2->next->next;
		cout << n1->value << " " << n2->value << endl;
		
		if(n1 == n2)
			return true;
	}while(n1 != head);
	return false;
}

int main()
{
	LinkedList L1;
	L1.addNode(5);
	L1.addNode(6);
	L1.addNode(7);
	L1.addNode(3);
	L1.addNode(1);
	L1.wrapAround();
	bool loopTest = L1.isCyclic();
	cout << "loop test is " << loopTest  << endl;

	return 0;
}

[funprogrammer]

@ciphermagi: Thanks a lot for that explanation. I tried your code but it not work either :(

I looked up online and found that I can do it with 3 pointers. I modified my code and it works with 3 pointers. I am scratching my head to see if it can be done using 2 pointers. iAny suggestion if we can implement Floyd's cycle finding algorithm using 2 pointers?

Here is the code for 3 pointers case:

bool LinkedList::isCyclic(){
   Node *n1, *n2, *n3;
   n1 = n2 = n3 = head;
   while(n1){
      n2 = n3->next;
      n3 = n2->next;
      if(n1==n2 || n1 == n3){
         return true;
      }
      n1 = n1->next;
   }
   return false;
}

[ciphermagi]

I did try to make it clear that my code (which was just basically a cleaning up of your own code) was going to work with a very, very limited case, and that it wouldn't actually work for anything else.

I see how this most recent isCyclic function could work, but it's pretty bastardized, and I don't think that it would like it very much if there was a massive loop that was possibly interior linked (multiple levels of loops, or a 3-D loop).

There are ways to implement the cycle-finding algorithm. You could probably find some of them referred to at stackexchange.

I'm going to be brutally honest with you, though. This is not a C++ problem that you're having. You're having a math problem. And you really need to study the algorithm itself, not the implementation of it, if you want to be able to do this. Once you fully understand the algorithm, and you can do the math involved, then you're going to find that (and I base this off of the level of code that I've seen you use here) the implementation with C++ will be ridiculously easy.