I want to detect loop in following cases
1-2-3-4-5
|----------| ===> case 1
1-2-3-4-5
|-------| ===> case 2
In case 1 cycle detection algorithm works correctly but not for case 2. I did dry run for case 2 I found that hare pointer ends normally. Also I thought that case 2 is not valid singly linked list as it contains 2 next pointer. Is my assumption correct for case 2? The whole scenario is for singly linked list?
Here is a solution for cycle detection that does not involve allocating heap memory:
struct Node {
int val;
struct node * next;
};
bool containsCycle(Node * head)
{
Node * walker = head;
NOde * fastWalker = head;
while(walker && fastWalker)
{
fastWalker = fastWalker->next;
if(walker == fastWalker)
return true;
if(fastWalker)
fastWalker = fastWalker->next;
if(walker == fastWalker)
return true;
walker = walker->next;
}
// Fell out of the loop, no cycle
return false;
}
This algorithm uses two pointers that advance at different speeds. If there is a cycle in the list, two of the pointers will at one point be equal to each other.
if(fastWalker) fastWalker = fastWalker->nextI'll give an answer based on a set of assumptions about what you are asking.
I'm guessing your formatting got messed up and you are using a singly-linked-list built from a node struct that has one pointer called "next."
I also assume that you have a pointer to the first element of the list, called Root.
Next, I assume that your algorithm consists of storing a copy of root, then walking the list to see if you get back to root.
This would work in a case like:
A -> B -> C -> D -> E //and E -> A.
But would not work if
A -> B -> C -> D -> E //and E -> B.
One way would be to mark each node visited as you walk along, either by adding a new field into the struct, or keeping a hashTable, then see if you get a repeat element.
(You could actually just add every tenth node into the hashtable, but check each visited node against the hashtable for duplicates).
If you know ahead of time how many elements are in the linked-list (and it isn't being modified), simple walk that many times and see if the next node is null.
