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
Recursive
Time complexity : O(n) Space complexity : O(1)
Time complexity : O(n) Space complexity : O(n)
Contributed by Nitin Ranganath