How to find the total number of items in linked list?

Question

I have a linked list which is cyclic and I want to find out the total number of elements in this list. How to achieve this?

Answer 1

One solution that I can think of is maintaining two pointers. First pointer (*start) will always point to the starting node, say Node A. The other pointer (*current) will be initialized as: current = start->next.

Now, just iterate each node with current -> next until it points to start. And keep incrementing a counter: numberOfNodes++;

The code will look like:

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 2

You just want to count the nodes in your linked list right? I've put an example below. But in your case there is a cycle so you also need to detect that in order not to count some of the nodes multiple times. I've corrected my answer there is now an ordinary count and count in loop (with a fast and slow pointer).

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;  
} 

Answer 3

Let's say the list has x nodes before the loop and y nodes in the loop. Run the Floyd cycle detection counting the number of slow steps, s. Once you detect a meet point, run around the loop once more to get y.

Now, starting from the list head, make s - y steps, getting to the node N. Finally, run two slow pointers from N and M until they meet, for t steps. Convince yourself (or better prove) that they meet where the initial part of the list enters the loop.

Therefore, the initial part has s - y + t + 1 nodes, and the loop is formed by y nodes, giving s + t + 1 total.

Answer 4

First find the cycle using Floyd Cycle Detection algorithm and also maintain count when you checking cycle once found loop then print count for the same.

    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 5

There is a "slow" pointer which moves one node at a time. There is a "fast" pointer which moves twice as fast, two nodes at a time.

A visualization as slow and fast pointers move through linked list with 10 nodes:

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

At this point one of two things are true: 1) the linked list does not loop (checked with fast != null && fast.next != null) or 2) it does loop. Let's continue visualization assuming it does loop:

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

If the linked list is not looped, the fast pointer finishes the race at O(n/2) time; we can remove the constant and call it O(n). If the linked list does loop, the slow pointer moves through the whole linked list and eventually equals the faster pointer at O(n) time.