• 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏吧

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

算法 来源:u449355 26次浏览

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

为如

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; 

版权声明:本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。
喜欢 (0)