算法 – 如何在链表循环中查找节点数?

如何在链表循环中找到节点数?

例如

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

找到从C到H的循环中的节点数

根本问题是如何找到C点.我们可以使用传统的野兔和乌龟算法,但它不会在C点每次都遇到.

我不认为我会认为这是一个linkList. LinkedLists通常以空指针或指向结束符号的指针结束.即:开始 – > A – > B – > C – >结束.我认为这将是一种特定的图形.

要查找图中的节点总数,我会这样做:

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;
相关文章
相关标签/搜索