如何查找链表中循环的节点数?
如何查找链表中的节点数量?如何查找链表中循环的节点数?
为如
A ----> B ----> C -----> D -----> E Λ |
| |
| V
H <----- G <----- F
查找由C至H
环路节点数目根本的问题是如何找到C点我们可以用传统的龟兔赛跑算法中,但它不每次都在C点见面。
回答:
我不认为我会认为这是一个linkedList。 LinkedLists通常以空指针或指向结尾符号的指针结束。即:start -> A -> B -> C -> end
。我认为这将是一种特定的图表。
为了找到节点图中的总人数,我会做这样的:
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
如果你总是知道会有一个循环一样(注意...
):
A ---> ... ---> C -----> D -----> E Λ |
| |
| V
... <----- G <--- F
你可以这样修改代码:
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;
回答:
如果你只是想找到答案,那么做龟兔来确定什么时候肯定有一个循环。然后启动一个计数器,并计算您必须进行多少次迭代才能达到您首次找到的点。这可能不是最有效的,但它给出了正确的答案。
一些C++代码:
#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;
}
请注意,你必须做一些额外的工作来确定,如果你打到最后,而不是循环,因为你实际上并没有一个周期的情况下。传统的乌龟,兔子应采取照顾:
http://en.wikipedia.org/wiki/Cycle_detection
回答:
请参阅如何找到一个链表循环here更多的解决方案。添加节点计数是非常简单的。 (虽然龟和野兔可能是最好的一个)
回答:
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
以上是 如何查找链表中循环的节点数? 的全部内容, 来源链接: utcz.com/qa/260820.html