Count Linked List Nodes

Given a singly linked list. The task is to find the length of the linked list, where length is defined as the number of nodes in the linked list.

Examples :

Input: LinkedList : 1->2->3->4->5

Output: 5
Explanation: Count of nodes in the linked list is 5, which is its length.

Input: LinkedList : 2->4->6->7->5->1->0
 
Output: 7
Explanation: Count of nodes in the linked list is 7. Hence, the output is 7.

Expected Time Complexity: O(n)
Expected Auxilliary Space: O(1)

Constraints:
1 <= number of nodes <= 10⁵
1 <= node->data <= 10³

Approach 01

class Solution {
  public:
    // Function to count nodes of a linked list.
    int getCount(struct Node* head) {
        int totalNodes = 0;
        struct Node* currentNode = head;
        
        while (currentNode != nullptr) {
            totalNodes++;
            currentNode = currentNode->next;
        }

        return totalNodes;
    }
};

class Solution:
    def getCount(self, head):
        totalNodes = 0
        currentNode = head
        
        while currentNode is not None:
            totalNodes += 1
            currentNode = currentNode.next
        
        return totalNodes

Time Complexity

• Iterating through the linked list:

  The algorithm traverses the entire linked list once, visiting each node exactly once. If there are n nodes in the linked list, this takes \(O(n)\) time.

• Overall Time Complexity:

  The time complexity of the function is \(O(n)\), where n is the number of nodes in the linked list.

Space Complexity

• Auxiliary Space:

  The algorithm uses a constant amount of extra space for variables like totalNodes and currentNode. No additional data structures are used.

• Overall Space Complexity:

  The space complexity is \(O(1)\), since the function only requires a constant amount of space regardless of the input size.