如何查找链表中循环的节点数?

如何查找链表中的节点数量?如何查找链表中循环的节点数?

为如

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

回到顶部