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.

Different Approaches

1️⃣ Iterative Approach

Intuition:

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.

2️⃣ Recursive Approach

Recursive Tree:

Code:

#include <iostream> // Include the input/output stream library

using namespace std; // Use the standard namespace for convenience

// Define a structure for a Node in the linked list
struct Node {
    int val;        // Value stored in the node
    Node* next;     // Pointer to the next node in the list

    // Constructor to initialize the node with a value and set 'next' to nullptr
    Node(int val) {
        this->val = val; // Assign the input value to the node
        next = nullptr;  // Initialize 'next' as null (end of the list by default)
    }
};

// Function to calculate the length of the linked list using recursion
int lengthUsingRecursion(Node* node) {
    // Base case: If the current node is null, return 0
    if (node == nullptr) {
        return 0;
    }

    // Recursive case: Return 1 (for the current node) + the length of the rest of the list
    return 1 + lengthUsingRecursion(node->next);
}

int main() {
    // Manually create the linked list by chaining nodes
    struct Node* head = new Node(1); // First node with value 1
    head->next = new Node(2);        // Second node with value 2
    head->next->next = new Node(3);  // Third node with value 3
    head->next->next->next = new Node(4); // Fourth node with value 4
    head->next->next->next->next = new Node(5); // Fifth node with value 5

    // Calculate and print the length of the linked list
    cout << "Length of the Linked List is: " << lengthUsingRecursion(head);

    // Note: The dynamically allocated memory is not freed here, but ideally, you should delete all nodes to avoid memory leaks
    return 0;
}

Complexity Analysis:

• Time Complexity: O(n)
  • As, we iterate over the whole linked list of size n.
• Space Complexity: O(n)
  • Due to the recursion stack.