how to find the number of nodes in a loop of linked list?
for e.g
A ----> B ----> C -----> D -----> E
Λ |
| |
| V
H <----- G <----- F
Find the number of nodes in a loop from C to H
Fundamental problem is how to find point C. We can use traditional hare and tortoise algo but it does not meet every time at point C.
See here more solutions for how to find a loop in a linked list. Adding the nodes counting is pretty simple then. (Although The Tortoise and the Hare is probably the best one)
If you simply want to find the answer, do the tortoise-hare to determine at what point there is definitely a loop. Then start a counter, and count how many iterations you must make to reach the point that you first found. This may not be the most efficient possible, but it gives a correct answer.
Some C++ code:
#include <iostream>
struct node
{
node(node* next)
: next(next)
{ }
node* next;
};
int main(int argc, char* argv[])
{
node h(NULL), g(&h), f(&g), e(&f), d(&e), c(&d), b(&c), a(&b);
h.next = &c;
node* tortoise = &a;
node* hare = &b;
while(tortoise != hare)
{
tortoise = tortoise->next;
hare = hare->next->next;
}
int count = 1;
tortoise = tortoise->next;
while(tortoise != hare)
{
++count;
tortoise = tortoise->next;
}
std::cout << "Size of cycle: " << count << "\n";
return 0;
}
Note that you'll have to do some extra work to determine if you hit the end, rather than looping, in the case that you don't actually have a cycle. Traditional tortoise-hare should take care of that:
List visited;
List toVisit;
toVisit.add(A); // add the first Node
while(toVisit is not empty){
Node current = visited.remove();
Array <Node> links = current.getLinks();
for(int i=0; i<links.size(); i++){
if(!visited.contains(links[i])){ // if the link has NOT already been visited add it to the toVisit List
toVisit.add(links[i]);
}
visited.add(current); // mark current as visited
}
}
return visited.size(); // to get the number of nodes in the graph
I don't think that I would consider this a linkedList. LinkedLists usually end with a null pointer or a pointer pointing to an ending symbol. Ie: start -> A -> B -> C -> end. I think that this would be a specific kind of graph.
To find the total number of nodes in the graph I would do this:
List visited;
List toVisit;
toVisit.add(A); // add the first Node
while(toVisit is not empty){
Node current = visited.remove();
Array <Node> links = current.getLinks();
for(int i=0; i<links.size(); i++){
if(!visited.contains(links[i])){ // if the link has NOT already been visited add it to the toVisit List
toVisit.add(links[i]);
}
visited.add(current); // mark current as visited
}
}
return visited.size(); // to get the number of nodes in the graph
If you always know that there will one loop like (note the ...):
A ---> ... ---> C -----> D -----> E
Λ |
| |
| V
... <----- G <--- F
You could modify the code like this:
List visited;
Node current = firstNode;
while(!visited.contains(firstNode)){
Node next = current.getNext();
visited.add(current); // mark current as visited
current=next;
}
// our ending condition is when we have found the same node again.
int currentIndex = visited.indexOf(current);
int size = visited.size();
int sizeOfLoop = size - currentIndex;
return sizeOfLoop;