Count nodes of linked list

Easy

0/40

Contributed by

58 upvotes

Asked in company

Problem statement

Given the head of a singly linked list of integers, find and return its length.

Example:

The length of the list is 4. Hence we return 4.

Note:

Exercise caution when dealing with edge cases, such as when the head is NULL. Failing to handle these edge cases appropriately may result in a runtime error in your code.

Detailed explanation ( Input/output format, Notes, Images )

Input format :

The first and only line contains elements of the singly linked list separated by a single space, -1 indicates the end of the singly linked list and hence, would never be a list element.

Output format :

Return a single integer denoting the length of the linked list.

Sample Input 1 :

3 4 5 2 6 1 9 -1

Sample Output 1 :

Explanation of sample input 1 :

The number of nodes in the given linked list is 7.
Hence we return 7.

Sample Input 2 :

10 76 39 -3 2 9 -23 9 -1

Sample Output 2 :

Expected Time Complexity:

Try to do this in O(n).

Constraints :

0 <= N <= 10^5
Time Limit: 1 sec

Hint 1

Linearly traverse the linked list.

Approaches (1)

Approach 1

Linear Traversal

The basic idea of this approach is to traverse the linked list.

Now consider the following steps:

It starts by initializing a variable ‘len’ to zero and a temporary pointer ‘temp’ to the ‘head’ of the list.
It then enters a loop that increments ‘len’ by one for each node in the list and moves the ‘temp’ pointer to the next node.
The loop continues until the end of the list is reached (when ‘temp’ becomes NULL).
Finally, the function returns the calculated length.

Time Complexity

O(N), where ‘N’ is the total number of nodes.

We are iterating the linked list. So the overall time complexity will be O(N).

Space Complexity

O(1)

We are using constant extra space. Hence, the overall space complexity is O(1).

(100% EXP penalty)

Count nodes of linked list

Console