Problem Statement

Given a linked list, we aim to find the total number of nodes (length) in the list.

Examples

Example1:

Input: list: 1 → 4 → 6
Output: 3
Explanation: The list has a total of 3 nodes, thus the length of the list is 3.

Approach

To find the length of a linked list, we need to traverse through all the nodes while keeping count of how many nodes we encounter. By the time we reach the end of the list (where the next pointer of the last node is null), the count represents the length of the list.

Algorithm:

1. Initialize a counter variable to zero.
2. Start from the head of the list.
3. While traversing the list:
   1. Increment the counter by one for each node visited.
   2. Move to the next node using the next pointer.
4. Once we reach the end of the list (where the next pointer is null), return the counter value as the length of the list.

Code:

#include <iostream>
using namespace std;

// Define the Node structure
class Node {
public:
    int data;
    Node* next;

    // Constructor
    Node(int value) {
        data = value;
        next = nullptr;
    }
};

// Function to find the length of the linked list
int findLength(Node* head) {
    int length = 0;
    Node* current = head;
    while (current != nullptr) {
        length++;
        current = current->next;
    }
    return length;
}

int main() {
    // Create a linked list
    Node* head = new Node(3);
    head->next = new Node(7);
    head->next->next = new Node(11);
    head->next->next->next = new Node(5);

    // Find the length of the linked list
    int length = findLength(head);

    // Print the length of the linked list
    cout << "Length of the linked list: " << length << endl;

    return 0;
}

// Output
Length of the linked list: 4

Complexity Analysis:

Time Complexity:O(n)

• The time complexity of finding the length of a linked list is linear with respect to the number of nodes in the list. This is because we need to traverse through all the nodes once to count them

Space Complexity: O(1)

• The space complexity is constant because the operation requires only a constant amount of additional memory for the counter variable, regardless of the size of the linked list.