Как узнать общее количество элементов в связанном списке?

Question

У меня есть связанный список, который является циклическим, и я хочу узнать общее количество элементов в этом списке.Как этого добиться?

Answer 1

Есть «медленный» указатель, который перемещает один узел за раз.Существует «быстрый» указатель, который перемещается вдвое быстрее, по два узла за раз.

Визуализация, когда медленные и быстрые указатели перемещаются по связанному списку с 10 узлами:

1: |sf--------|
2: |-s-f------|
3: |--s--f----|
4: |---s---f--|
5: |----s----f|

Вв этом пункте одна из двух вещей верна: 1) связанный список не зацикливается (проверяется с помощью fast! = null && fast.next! = null) или 2) он зацикливается.Давайте продолжим визуализацию, предполагая, что это делает цикл:

6: |-f----s---|
7: |---f---s--|
8: |-----f--s-|
9: |-------f-s|
10: s == f

Если связанный список не зациклен, быстрый указатель заканчивает гонку в O (n / 2) время;мы можем удалить константу и назвать ее O (n).Если связанный список выполняет цикл, медленный указатель перемещается по всему связанному списку и, в конечном итоге, становится равным более быстрому указателю в момент времени O (n).

Answer 2

Сначала найдите цикл, используя алгоритм Floyd Cycle Detection, а также сохраняйте счет при проверке цикла, когда цикл найден, а затем напечатайте счет для того же самого.

    function LinkedList() {
      let length = 0; 
      let head = null; 

      let Node = function(element) {
        this.element = element; 
        this.next = null;
      }

      this.head = function() {
        return head;
      };

    this.add = function(element) {
      let node = new Node(element);
      if(head === null){
          head = node;
      } else {
          let currentNode = head;
          while(currentNode.next) {
              currentNode = currentNode.next;
          }
          currentNode.next = node;
      }
    };
      this.detectLoopWithCount = function() {
        head.next.next.next.next.next.next.next.next = head; // make cycle
        let fastPtr = head;
        let slowPtr = head;
        let count = 0;
        while(slowPtr && fastPtr && fastPtr.next) {
          count++;
          slowPtr = slowPtr.next;
          fastPtr = fastPtr.next.next;
          if (slowPtr == fastPtr) {
            console.log("\n Bingo :-) Cycle found ..!! \n ");
            console.log('Total no. of elements = ', count);
            return;
          }
        }
      }
    
    }
    let mylist = new LinkedList();
      mylist.add('list1');
      mylist.add('list2');
      mylist.add('list3');
      mylist.add('list4');
      mylist.add('list5');
      mylist.add('list6');
      mylist.add('list7');
      mylist.add('list8');
      mylist.detectLoopWithCount();

Answer 3

Допустим, в списке есть x узлов перед циклом и y узлов в цикле.Запустите обнаружение цикла Флойда, считая количество медленных шагов, s.Как только вы обнаружите точку встречи, еще раз обойдите цикл, чтобы получить y.

Теперь, начиная с заголовка списка, сделайте s - y шагов, добравшись до узла N.Наконец, запустите два медленных указателя от N и M, пока они не встретятся, для шагов t.Убедите себя (или лучше докажите), что они встречаются там, где начальная часть списка входит в цикл.

Следовательно, начальная часть имеет s - y + t + 1 узлов, а цикл состоит из y узлов, даваяs + t + 1 всего.

Answer 4

Одним из решений, о котором я могу думать, является поддержание двух указателей.Первый указатель (* start) всегда будет указывать на начальный узел, скажем, на узел A. Другой указатель (* current) будет инициализирован как: current = start-> next.

Теперь просто итерируйте каждый узел с помощьютекущий -> следующий, пока он не укажет на начало.И продолжайте увеличивать счетчик: numberOfNodes ++;

Код будет выглядеть так:

public int countNumberOfItems(Node* start){
Node* current = start -> next;

int numberOfNodes = 1; //Atleast the starting node is there.

while(current->next != start){
   numberOfNodes++;
   current = current->next;
}
return numberOfNodes; 
}

Answer 5

Вы просто хотите считать узлы в вашем связанном списке, верно?Я привел пример ниже.Но в вашем случае есть цикл, поэтому вам также нужно обнаружить его, чтобы не считать несколько узлов несколько раз.Я исправил свой ответ, теперь есть обычный подсчет и подсчет в цикле (с быстрым и медленным указателем).

static int count( Node n)  
{  
    int res = 1;  
    Node temp = n;  
    while (temp.next != n)  
    {  
        res++;  
        temp = temp.next;  
    }  
    return res;  
}  

static int countInLoop( Node list)  
{  
    Node s_pointer = list, f_pointer = list;  

    while (s_pointer !=null && f_pointer!=null && f_pointer.next!=null)  
    {  
        s_pointer = s_pointer.next;  
        f_pointer = f_pointer.next.next;  

        if (s_pointer == f_pointer)  
            return count(s_pointer);  
    }  

    return 0;  
}