Как найти количество узлов в цикле связанного списка?

Question

как найти количество узлов в цикле связанного списка?

, например,

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

Найти число узлов в цикле от C до H

Основная проблема заключается в том, как найти точку C. Мы можем использовать традиционныеАлго черепаха, но он не встречается каждый раз в точке C.

Answer 1

См. здесь другие решения о том, как найти цикл в связанном списке.Добавить подсчет узлов довольно просто.(Хотя Черепаха и Заяц, вероятно, лучший)

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

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

Answer 4

1) flyod alogo найти цикл 2) когда slow_ptr = fast_ptr, найти количество узлов в цикле (k)

Кроме того, вы также можете перейти к C следующим образом: - 3) start 2 ptr,один из головы и другой из головы + к.4) Вы встретитесь при старте Loop (C)

Answer 5

Не думаю, что считаю это связанным списком.Списки 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;