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

Question

如何查找链表中的节点数量？

为如

A ----> B ----> C -----> D -----> E 
       Λ     | 
       |     | 
       |     V 
       H <----- G <----- F 

查找由C至H

环路节点数目

根本的问题是如何找到C点我们可以用传统的龟兔赛跑算法中，但它不每次都在C点见面。

Answer 1

我不认为我会认为这是一个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; 

Answer 2

如果你只是想找到答案，那么做龟兔来确定什么时候肯定有一个循环。然后启动一个计数器，并计算您必须进行多少次迭代才能达到您首次找到的点。这可能不是最有效的，但它给出了正确的答案。

一些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

Answer 3

请参阅如何找到一个链表循环here更多的解决方案。添加节点计数是非常简单的。 （虽然龟和野兔可能是最好的一个）

Answer 4

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