Counting the Nodes

Iterative and recursive way of counting the number of nodes in a linked list.

Iterative Method :

int count(struct node *ptr) {

    // A variable to keep track of count
    int count = 0;

    // Iterate till ptr becomes NULL
    while (ptr != NULL) {
        count++;
        ptr = ptr -> next;
    }
    return count;

}

Recursive Method :

int count(struct node *ptr) {

    // Base condition for termination
    if (ptr == NULL) {
        return 0;
    }
    // Recursive call 
    else {
        return count(ptr -> next) + 1;
    }

}

Time and Space Complexity :

Iterative

Time complexity : O(n) Space complexity : O(1)

Recursive

Time complexity : O(n) Space complexity : O(n)

Contributed by Nitin Ranganath